动态规划(Dynamic Programming，DP)

以问题 "爬台阶" 为例, 题目如下:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

• 1 <= n <= 45

力扣: https://leetcode.cn/problems/climbing-stairs/.

注意: 下文中的 "步", 与上面题目里的 "step" 含义不同.

测试用例

fn main() {
    assert_eq!(climb_stairs(2), 2);
    assert_eq!(climb_stairs(3), 3);
    assert_eq!(climb_stairs(5), 8);
    assert_eq!(climb_stairs(18), 4181);
}

暴力搜索(Brute-force search)

题目要求实现函数 climb_stairs, 以下使用函数 \(f\) 表示.

• 从第 0 级台阶到达第 1 级台阶, 共一种爬法, 即一次爬一级台阶. 因此 \(f(1) = 1\).
• 从第 0 级台阶到达第 2 级台阶, 共两种爬法, 一次爬一级台阶或两级台阶. 因此 \(f(2) = 1 + 1 = 2\).

\(f(1)\) 和 \(f(2)\) 的结果很好计算, 因为都只需要爬一次台阶. 但从 \(f(3)\) 开始, 至少需要爬两次台阶.

• 从第 1 级台阶到达第 3 级台阶, 共一种爬法, 即一次爬两级台阶.
• 从第 2 级台阶到达第 3 级台阶, 共一种爬法, 即一次爬一级台阶.

因此计算 \(f(3)\) 可以利用到 \(f(1)\) 和 \(f(2)\) 的值. 得到状态转移方程:

\[ f(n) = f(n-1) + f(n-2) \]

pub fn climb_stairs(n: i32) -> i32 {
    assert!(1 <= n && n <= 45);
    if n == 1 || n == 2 {
        n
    } else {
        climb_stairs(n - 1) + climb_stairs(n - 2)
    }
}

时间复杂度为 \(O(2^n)\), 空间复杂度为 \(O(n)\).

该算法实现的最大问题在于其时间复杂度是指数级别的.

记忆化搜索(Memoization)

上面暴力搜索的实现存在大量重复性计算:

• \(f(n) = f(n-1) + f(n-2)\)
• \(f(n-1) = f(n-1-1) + f(n-2-1) = f(n-2) + f(n-3)\)

其中 \(f(n-2)\) 将被重复计算, 可以通过缓存函数的计算结果来避免重复计算.

pub fn climb_stairs(n: i32) -> i32 {
    assert!(1 <= n && n <= 45);
    climb_stairs_inner(n, &mut HashMap::from([(1, 1), (2, 2)]))
}

fn climb_stairs_inner(n: i32, cache: &mut HashMap<i32, i32>) -> i32 {
    // 检查缓存中是否已存在计算结果, 若有直接返回结果, 避免重复计算
    if let Some(value) = cache.get(&n) {
        // 缓存命中
        return *value;
    }
    let result = climb_stairs_inner(n - 1, cache) + climb_stairs_inner(n - 2, cache);
    // 缓存计算结果
    cache.insert(n, result);
    result
}

时间复杂度为 \(O(n)\), 空间复杂度为 \(O(n)\).

这样计算 \(f(n)\) 只需要计算 \(f(n - 1), f(n - 2) ..., f(1)\). 所以时间复杂度为 \(O(n)\).

递推

• \(f(n) = f(n-1) + f(n-2)\)
• \(f(n-1) = f(n-2) + f(n-3)\)
• \(f(n-2) = f(n-3) + f(n-4)\)
• \(...\)
• \(f(2) = 2\)
• \(f(1) = 1\)

\[ \begin{align} 计算 f(n) \rightarrow 计算 f(n-1), f(n-2) \rightarrow 计算 f(2), f(1) \end{align} \]

\[ \begin{align} 计算 f(2), f(1) \rightarrow 计算 f(n-1), f(n-2) \rightarrow 计算 f(n) \end{align} \]

若利用递归算法自上而下的方法(Top-down approach)依次求值(1)会产生重复计算, 但改变求值顺序, 使用自下而上的方法(Bottom-up approach)求值(2)则可以避免该问题.

pub fn climb_stairs(n: i32) -> i32 {
    assert!(1 <= n && n <= 45);
    let mut f = vec![0, 1];
    for _ in 0..n as usize {
        f.push(f[f.len() - 1] + f[f.len() - 2]);
    }
    f[n as usize + 1]
}

时间复杂度为 \(O(n)\), 空间复杂度为 \(O(n)\).

改进后的算法不再需要通过缓存来避免重复计算, 而且不再使用递归.

通过观察先前的公式, 可以发现第 n 行的值等于第 n-1 行的值加上第 n-2 行的值.
因此只需要存储前两次的计算结果:

pub fn climb_stairs(n: i32) -> i32 {
    assert!(1 <= n && n <= 45);
    let mut f0 = 0;
    let mut f1 = 1;
    for _ in 0..n {
        let f2 = f1 + f0;
        f0 = f1;
        f1 = f2;
    }
    f1
}

时间复杂度为 \(O(n)\), 空间复杂度为 \(O(1)\).

可以看出该算法和斐波那契数列(Fibonacci sequence)的实现一致.

拓展

• https://www.youtube.com/watch?v=aPQY__2H3tE

评论