动态规划(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 stepsExample 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 stepConstraints:
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)\) 的值. 得到状态转移方程:
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\)
若利用递归算法自上而下的方法(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)的实现一致.