algorithms►leetcode

028-爬楼梯（DP Fibonacci）

爬楼梯

1. 问题本质分析

  • 问题描述：每次可以爬 1 或 2 个台阶，求爬到第 n 阶的方法数。
  • 实际意义：该问题等价于 斐波那契数列，因为：
    • 到达第 n 阶的方法数 = 从 n-1 阶爬 1 步的方法数 + 从 n-2 阶爬 2 步的方法数。
    • 即：f(n) = f(n-1) + f(n-2)。

2. 动态规划的核心思想

(1) 定义状态
  • dp[i]：表示爬到第 i 阶台阶的方法数。
(2) 状态转移方程
dp[i] = dp[i-1] + dp[i-2]
  • 解释：
    • 从 i-1 阶爬 1 步到达 i 阶。
    • 从 i-2 阶爬 2 步到达 i 阶。
(3) 初始化
dp[0] = 1  // 初始状态（地面）
dp[1] = 1  // 第1阶只有1种方法（爬1步）
dp[2] = 2  // 第2阶有2种方法（1+1或直接2）

3. 代码实现与逐步解析

(1) 基础动态规划（空间复杂度 O(n)）
1
2
3
4
5
6
7
8
9
10
var climbStairs = function(n) {
    if (n <= 2) return n;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1; // 初始状态
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)（存储整个 dp 数组）
(2) 优化空间（空间复杂度 O(1)）
1
2
3
4
5
6
7
8
var climbStairs = function(n) {
    if (n <= 2) return n;
    let a = 1, b = 2; // a=dp[i-2], b=dp[i-1]
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, a + b]; // 状态转移
    }
    return b;
};
  • 优化原理：
    只需保存前两个状态（dp[i-1] 和 dp[i-2]），无需存储整个数组。

4. 为什么动态规划比递归更优？

方法 时间复杂度 空间复杂度 缺点
递归 O(2ⁿ) O(n) 重复计算导致超时
记忆化递归 O(n) O(n) 需要额外空间存储中间结果
动态规划 O(n) O(1) 最优解
  • 递归的问题：
    计算 f(5) 时会重复计算 f(3) 和 f(4)，导致指数级复杂度。
  • 动态规划的优势：
    通过递推公式 自底向上 计算，避免重复计算。

5. 分步示例（n=5）

i a (dp[i-2]) b (dp[i-1]) 更新后 [a, b]
3 1 2 [2, 3]
4 2 3 [3, 5]
5 3 5 [5, 8]
  • 最终结果：b = 8（即 f(5)=8）

6. 数学本质

  • 斐波那契数列：1, 1, 2, 3, 5, 8, 13...
    • f(n) = f(n-1) + f(n-2)
    • 爬楼梯问题是斐波那契数列的变种（初始条件不同）。

7. 如何想到动态规划？

  1. 识别重叠子问题：
    • 计算 f(5) 需要 f(4) 和 f(3)，而 f(4) 又需要 f(3) 和 f(2)，存在大量重复计算。
  2. 定义状态：
    • 用 dp[i] 表示问题的子解。
  3. 建立状态转移：
    • 通过问题规律（如 dp[i] = dp[i-1] + dp[i-2]）递推。

8. 边界条件处理

  • n=0：返回 1（地面算一种方法）。
  • n=1：返回 1（只有一种爬法）。
  • n=2：返回 2（1+1 或直接 2）。

总结

  • 动态规划适用场景：
    问题具有 最优子结构 和 重叠子问题 特性。
  • 爬楼梯的关键：
    将大问题分解为小问题，通过递推公式避免重复计算。
  • 优化核心：
    用有限变量代替数组，将空间复杂度从 O(n) 降至 O(1)。