爬楼梯

问题拆解

每次爬 1 阶或 2 阶，问爬到第 n 阶有多少种走法。

换个角度看结尾：到达第 n 阶的最后一步，要么是从 n-1 阶跨 1 步，要么是从 n-2 阶跨 2 步。这两种情况互不重叠，也覆盖了所有可能。所以：

f(n) = f(n-1) + f(n-2)

再配上边界 f(1) = 1、f(2) = 2，这正是斐波那契数列。

找到“最后一步只有几种来源”，递推式就浮出来了——这是很多计数型 DP 的入口。

从递归到滚动变量

直接按定义写递归会超时：f(n) 要算 f(n-1) 和 f(n-2)，而 f(n-1) 又要算一遍 f(n-2)，同一个子问题被重复计算，规模呈指数级膨胀。

加记忆化能把它降到 O(n)，但其实还能更省。注意算 f(n) 只需要前两个值，不必保留整张表，于是用两个变量滚动就够了：

def climbStairs(n: int) -> int:
    prev, cur = 1, 1  # 分别代表 f(i-1) 和 f(i)

    for _ in range(n - 1):
        prev, cur = cur, prev + cur

    return cur

我把 f(0) 和 f(1) 都设成 1（爬 0 阶只有“不动”这一种走法），这样循环从 f(1) 递推到 f(n)，边界更统一。每一步 cur 前进一位，prev 跟上，空间从 O(n) 压到 O(1)。

复杂度

指标	复杂度	原因
时间	O(n)	从 1 递推到 n，每阶算一次
空间	O(1)	只保留相邻两个状态

可以迁移的模式

• 计数问题：“到达某状态的方法数”常常等于“各个前驱状态方法数之和”；
• 先写出朴素递归，看到重叠子问题就上记忆化；
• 若递推只依赖最近几个状态，就用滚动变量把整张表压掉。

“递归超时 → 记忆化 → 滚动数组”是 DP 优化的常规三级跳，爬楼梯是把这条路走一遍的最短例子。