爬楼梯

动态规划（Dynamic Programming）入门#

题目描述#

方案：滚动数组优化（动态规划）#

核心思路： 要到达第 n 阶，最后一步只有两种可能：

• 从第 n-1 阶跨 1 步上来（共有 f(n-1) 种方法）。
• 从第 n-2 阶跨 2 步上来（共有 f(n-2) 种方法）。 因此，状态转移方程为：$f(n) = f(n-1) + f(n-2)$。这正是著名的斐波那契数列。

1
class Solution {
2
public:
3
    int climbStairs(int n) {
4
        if (n <= 1) return 1;
5

6
        // 使用三个变量进行滚动更新，将空间复杂度降至 O(1)
7
        int a = 1; // f(n-2)
8
        int b = 1; // f(n-1)
9
        int c = 0; // f(n)
10

11
        for (int i = 2; i <= n; ++i) {
12
            c = a + b; // 当前阶 = 前两阶之和
13
            a = b;     // 窗口向右滚动
14
            b = c;
15
        }
16
        return b;
17
    }
18
};

常见问答#

Q：为什么不用纯递归？ A：纯递归会产生大量的重复计算（如计算 f(5) 需要 f(4) 和 f(3)，计算 f(4) 又需要 f(3)…）。这会导致时间复杂度爆炸（指数级 $O(2^n)$），当 $n > 40$ 时基本会超时。

Q：如果每次可以爬 1、2、3 步呢？ A：同理推导出方程 $f(n) = f(n-1) + f(n-2) + f(n-3)$，只需要增加一个初始化状态即可。

总结#

• 状态转移是核心：找到“最后一步”的逻辑，就能写出方程。
• 空间优化：当当前状态只依赖于前几个固定状态时，用变量替代数组是极佳的性能优化。