LeetCode 70. 爬楼梯：动态规划的第一课

爬楼梯（LeetCode 70）被 labelled 为「简单」，但它的地位远超难度标签：它是无数人动态规划的第一课——题面短到三行，却完整包含了 DP 的全部要素：状态定义、递推关系、边界、以及「别用裸递归」的教训。

题面与约束

你正在爬楼梯，需要 n 阶才能到达楼顶。每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶？

数据范围：1 <= n <= 45。这个 45 不是随便定的——后文揭晓它正好卡在 32 位整数的溢出线上。

递推式：从最后一步倒推

到达第 n 阶的最后一步只有两种可能：从第 n-1 阶跨 1 阶上来，或从第 n-2 阶跨 2 阶上来。这两类方案互不重叠、合并起来又完备，所以：

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

边界：f(1) = 1（一阶只有一种），f(2) = 2（两阶：1+1 或 2）。眼熟吗？这就是斐波那契数列的变体——爬楼梯的本质是「带初始条件的斐波那契」。

三级演化：从会跑到跑得优雅

第一级：裸递归（会超时）。直接翻译递推式，f(n) = f(n-1) + f(n-2)，代价是指数级的重复计算——f(45) 需要数十亿次函数调用，LeetCode 上必然超时。它是理解递推的脚手架，不是答案。

第二级：记忆化 / DP 数组（O(n) 时间、O(n) 空间）。把算过的 f 存进数组，每项只算一次。

第三级：滚动变量（O(n) 时间、O(1) 空间）。注意到 f(n) 只依赖前两项，两个变量滚动即可——这就是最终提交形态：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2              # a = f(i-2), b = f(i-1)
        for _ in range(3, n + 1):
            a, b = b, a + b      # 滚动前进
        return b

这个「滚动变量」模式值得单独记住：凡是递推只依赖常数个前驱的 DP，都可以把数组压成几个变量。它是从「会做 DP」到「写好 DP」的第一步。

本地验证

代码在本地跑通，包括与朴素递归的前 20 项逐项对照（1, 2, 3, 5, 8, 13, … 完全一致），以及约束上限的检验：f(45) = 1836311903。

from functools import lru_cache

@lru_cache(None)
def naive(n):                    # 朴素递归，仅用于小规模对照
    return n if n <= 2 else naive(n - 1) + naive(n - 2)

s = Solution()
assert all(s.climbStairs(n) == naive(n) for n in range(1, 21))
assert s.climbStairs(45) == 1836311903

为什么是 45：一条精心设计的溢出线

f(45) = 1836311903，而 32 位有符号整数的上限是 2147483647——f(45) 是不超过它的最后一项，f(46) = 2971215073 就溢出了。LeetCode 把 n 限到 45，正是为了让所有语言的 int 都安全；如果题目给到 n = 100，你就得换 64 位整数或大数——同一道题在「语言层面的坑」上立刻换了难度。顺便，n 很大时还有一条数学捷径：用矩阵快速幂或斐波那契闭式解，O(log n) 就能算出 f(n)，不过对本题约束属于杀鸡用牛刀。

DP 思维的三件套，这题全有

状态：f(n) = 到达第 n 阶的方案数——定义得干净，后面全是机械劳动；
转移：f(n) = f(n-1) + f(n-2)——来自「最后一步」的分类讨论，互斥且完备；
实现优化：依赖关系局部（只看前两项）→ 空间可压缩。

后续进阶题（打家劫舍、最小花费爬楼梯）都是在这三件套上做变体：转移里加约束、状态里加维度。把爬楼梯想透了，等于拿到了 DP 入门系列的钥匙。

参考资料

LeetCode 70. 爬楼梯 — 题目页
LeetCode 官方题解：动态规划
本文代码已本地跑通（与朴素递归 20 项对照 + 上限 n=45 验证）