刷到 LeetCode Hot 100 题单的人绝大多数会在第 70 题“爬楼梯”这里停一下。不是因为它难恰恰相反是它太简单了简单到让人怀疑自己是不是看错了题单每次可以爬 1 阶或 2 阶爬 n 阶楼梯有多少种方法就这么一句话。但你要是真把它当成一道“背公式”的水题后面吃亏的机会就大了。Hot 100 里这道题被放在很靠前的位置不是为了让你一眼认出斐波那契数列而是为了用最小的问题模型逼你把动态规划从“听懂了”变成“真的会写”。这篇文章我按自己刷题时的完整思考路径来聊先暴力递归、再记忆化搜索、然后标准 DP、最后滚动数组再顺手讲讲矩阵快速幂和几个高频率变形题。不论你是刚接触动态规划还是已经在刷第二轮 Hot 100肯定都能从中抠出点东西。1. 先搞清楚爬楼梯到底是哪个环节的题目1.1 题目重述与输入输出LeetCode 70. 爬楼梯题面非常简单假设你正在爬楼梯需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶你有多少种不同的方法可以爬到楼顶呢输入n 2 输出2 解释有两种方法可以爬到楼顶 1. 1 阶 1 阶 2. 2 阶 输入n 3 输出3 解释有三种方法 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶注意 n 的范围LeetCode 原题给的是1 n 45。很多新手看到这个范围第一反应是“那直接递归也能过吧”对确实能过但那是题目的仁慈不是你的本事。1.2 这道题在 Hot 100 里的真正定位我一直觉得 Hot 100 的题目顺序是有讲究的。爬楼梯被放在 70 题这种靠前位置恰好是大多数刷题人从“会写循环”到“理解状态转移”的转折点。它不像后面的打家劫舍、编辑距离那样有复杂的决策过程也不像背包问题那样需要选二维状态。爬楼梯的核心递推关系只有一句话到第 i 阶的方法数等于到第 i-1 阶的方法数加上到第 i-2 阶的方法数。但就是这一句话把“分治思想”和“动态规划思想”的区别、自顶向下和自底向上的区别、空间换时间的取舍这些概念全串起来了。我见过不少人直接一行斐波那契公式把题目过了然后做后面 746 题最小花费爬楼梯时卡住。原因很简单他没理解递推的起点只记住了公式的终点。1.3 一个必须先纠正的直觉很多人第一眼会想“爬 1 阶有 1 种爬 2 阶有 2 种那爬 3 阶就是 3 种爬 4 阶就是 5 种……这不就是斐波那契嘛” 对也不是。对的地方在于数字确实长这样不对的地方在于这是一个观察结论不是推导逻辑。你要是只记住“f(n) f(n-1) f(n-2)”那面试官追问一句“为什么不是每步走 1、2、3 阶的情况”你如果只会套斐波那契就露馅了。所以我们从更朴素的“最后一步”出发你要到第 n 阶倒数第一步要么站在第 n-1 阶迈 1 阶要么站在第 n-2 阶迈 2 阶。这两种情况互不重叠而且覆盖了所有可能性所以总数就是两者之和。这个逻辑不光对 1 和 2 有效对 1、2、3 也一样成立只是变成三项相加。2. 先把错误答案写一遍暴力递归的惨痛教训2.1 三行代码的诱惑如果没学过动态规划最直接的做法是写递归。用数学表达式就是f(1) 1 f(2) 2 f(n) f(n-1) f(n-2)翻译成 Python 就是三行def climbStairs(n: int) - int: if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这段代码在 n 很小的时候跑得飞快看上去完全没问题。我在本地测试的时候n10秒出n30能感觉到等待n45直接风扇狂转——等了几十秒还没返回结果。问题就出在这里。2.2 递归树里藏着的指数灾难以f(6)为例它的执行过程会调用f(5)和f(4)而f(5)又会调用f(4)和f(3)f(4)被重复计算了两次。画出来的递归树越往下越膨胀每个节点都分裂出两个子节点整个树的节点数大约是2^n数量级。我们来算一笔具体账f(45)的调用次数粗略估计为2^45量级大约 35 万亿。一台普通笔记本每秒能执行上亿次简单函数调用你自己算算这要跑多久。就算每次调用只要 1 纳秒也要 3.5 万秒整整 10 个小时。实际情况当然没这么夸张因为中间会有重复子树的合并效应但 n45 时跑几十秒是实实在在的。提示暴力递归的时间复杂度是 O(2^n)空间复杂度是 O(n)递归调用栈深度不是 O(1)。2.3 重复计算是唯一的敌人暴力递归慢不是因为递归本身慢而是因为同样的子问题被算了无数遍。f(n-2)在f(n-1)的递归里会被算一次在f(n)的另一个分支里又会被算一次。层次越深重复越严重。这就引出了两个优化方向一是把算过的结果存下来下次直接用记忆化搜索二是不走递归直接从底往上推保证每个子问题只算一次动态规划。这两种思路本质是同一个东西的两种形式面试时能说清这一点往往比直接甩代码更让面试官认可。3. 记忆化搜索让递归聪明起来的第一种方法3.1 给递归加一个缓存既然重复计算是痛点最简单的改造就是加一个 memo 字典。递归进来先查表有就直接返回没有就算完存起来。def climbStairs(n: int) - int: memo {} def dfs(i: int) - int: if i 2: return i if i in memo: return memo[i] memo[i] dfs(i - 1) dfs(i - 2) return memo[i] return dfs(n)严格来说这个写法里每个f(i)都只会在第一次被真正递归计算之后全部是 O(1) 的查表操作。整个复杂度立刻降到 O(n) 时间、O(n) 空间。n45 在这种写法下瞬间返回。3.2 自顶向下 vs 自底向上记忆化搜索的思考路径是从目标出发“我要 f(n)需要 f(n-1) 和 f(n-2)”一路拆解到已知的 base case。这种方向叫自顶向下和人类思考问题的方式很像所以特别好理解。但这里有一个隐藏的坑递归深度。Python 默认递归深度限制在 1000 层左右虽然这题 n 只有 45完全够用但如果题目改成 n 2000即使你有 memo 也会因为超过递归深度而报错RecursionError。所以要记住记忆化搜索好用但受制于递归深度。这也是为什么多数竞赛和面试标准答案都会采用自底向上的写法。4. 标准动态规划写法从底往上推到楼顶4.1 dp 数组的直观理解动态规划的典型写法是开一个 dp 数组dp[i]表示到达第 i 阶的方法总数。初始条件是dp[1] 1爬 1 阶只有一种方式dp[2] 2一阶一阶爬或者一步跨两阶。转移方程就是我们在前面反复强调的dp[i] dp[i - 1] dp[i - 2]这段代码的核心是循环没有任何递归调用def climbStairs(n: int) - int: if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]4.2 为什么初始条件不能拍脑袋很多初学者会把dp[0]也设为 1理由是为了让dp[2] dp[1] dp[0] 1 1 2成立。这种写法本身没有毛病但你需要想清楚dp[0]到底代表什么。如果说“到第 0 阶有 1 种方法”那其实是定义了一种“空状态”——你站在地面上不爬也是一种方案。这在数学上是为了统一递推公式的边界但在面试现场你如果解释不清楚反而会扣分。我个人更推荐从dp[1]和dp[2]起步因为这两个值的直觉太明显了一个台阶只有一种爬法两个台阶有两种爬法。从明确的物理意义出发能减少边界条件的混淆。4.3 把数组压缩成两个变量滚动数组精讲我们再观察一下转移方程dp[i] dp[i-1] dp[i-2]。计算dp[i]只用到前两个值算完dp[i]之后dp[i-2]就再也没用了。既然这样我们根本不需要一个长度为 n 的数组只要两个变量不断往前滚动就行。def climbStairs(n: int) - int: if n 2: return n prev1, prev2 1, 2 # prev1 dp[1], prev2 dp[2] for _ in range(3, n 1): cur prev1 prev2 prev1, prev2 prev2, cur return prev2这个写法的时间复杂度仍然是 O(n)但空间复杂度降到了 O(1)。面试时如果先讲了 dp 数组版本再补一句“其实这题还能滚动数组压缩到常数空间”会显得你对状态设计有感知。这里有一个很多人写错的小细节prev1, prev2 prev2, cur这种并行赋值在 Python 里是先计算右边再赋值天然安全但在 C 或 Java 里如果写prev1 prev2; prev2 cur;你需要注意prev1拿到的其实是旧prev2这恰好是我们想要的滚动效果。如果你不小心写完顺序反了就变成prev1 prev2; prev2 prev1 prev2递推直接崩掉。5. 进阶玩法矩阵快速幂和通项公式5.1 当 n 变大到 10^18 时O(n) 也扛不住LeetCode 原题的 n 只有 45O(n) 的滚动数组已经是完美答案了。但如果你参加竞赛题目可能会变成“n 10^18”这种级别这时候 O(n) 也是死路一条。好在爬楼梯这种二阶线性递推可以用矩阵乘法来表示[f(n) ] [1 1] [f(n-1)] [f(n-1)] [1 0] [f(n-2)]也就是说每次递推相当于左乘一个 2×2 的矩阵 M。从初始向量[f(2), f(1)]出发要得到[f(n1), f(n)]就把 M 自乘 n-1 次。而矩阵自乘可以用快速幂做到 O(log n)于是整个算法的时间复杂度就是 O(log n)。5.2 矩阵快速幂的 Python 实现计算 2×2 矩阵乘法手写也不复杂def climbStairs(n: int) - int: if n 2: return n def mul(a, b): return [ [a[0][0] * b[0][0] a[0][1] * b[1][0], a[0][0] * b[0][1] a[0][1] * b[1][1]], [a[1][0] * b[0][0] a[1][1] * b[1][0], a[1][0] * b[0][1] a[1][1] * b[1][1]] ] def pow_mat(mat, power): res [[1, 0], [0, 1]] # 单位矩阵 while power: if power 1: res mul(res, mat) mat mul(mat, mat) power 1 return res M [[1, 1], [1, 0]] res pow_mat(M, n - 1) return res[0][0] res[0][1] # 具体计算方式见下面说明这段代码里最后的返回需要根据初始向量来定。用[f(2), f(1)] [2, 1]作为初始向量乘上 M 的 n-2 次方后结果的第一个元素就是 f(n)。调试时建议先还原成 f(3)、f(4) 手工验证。5.3 特征方程求通项公式知道但别滥用因为递推公式是线性的我们可以通过特征方程x^2 x 1解出通项公式也就是斐波那契数列的通项变体f(n) (phi^(n1) - psi^(n1)) / sqrt(5) phi (1 sqrt(5)) / 2 psi (1 - sqrt(5)) / 2理论上这个公式能 O(1) 求结果但实际工程里sqrt(5)是浮点数n 稍大一点就会因为浮点误差导致结果不精确。就算用round修正也有风险。我自己只在两种情况下用通项公式一是在论文里为了展示数学推导二是在高频交易或量化场景中需要近似值。刷题或面试时用通项公式反而是最不推荐的答案因为它掩盖了你对递推本质的掌握程度。提示如果题目要求结果对 1e97 取模矩阵快速幂是标准做法通项公式中的浮点运算没法直接处理取模。6. 变形题才是真正的价值从 70 到 746 再到面试追问6.1 变形一每次可以爬 1、2、3 阶怎么办这是最容易举一反三的变体。还是从最后一步出发到第 n 阶最后一步要么从 n-1 迈 1 阶要么从 n-2 迈 2 阶要么从 n-3 迈 3 阶。于是递推变成dp[i] dp[i-1] dp[i-2] dp[i-3]初始条件变成了 1、2、4。这种“分析最后一步”的习惯能覆盖所有类似的爬楼梯变体。面试官看到你主动推导而不是背公式往往会高看一眼。6.2 变形二LeetCode 746 最小花费爬楼梯Hot 100 里邻近的一道题和 70 题联动极强。题目说每阶都有花费 cost[i]你可以从第 0 阶或第 1 阶开始每次爬 1 或 2 阶求到达楼顶的最小花费。关键区别是70 求方案总数746 求最优方案所以要改成 min。状态转移是dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])其中 dp[i] 表示“到达第 i 阶之前已经付出的最小花费”。注意这里路径上有费用而不是在节点上结算。很多人在 746 摔倒就是因为没搞清楚“到第 i 阶花费的是第 i 阶的费用”还是“到达第 i 阶后累计费用是 dp[i]”。我的建议是把 dp[i] 定义为“到达第 i 阶的累计花费”起点是 dp[0] 0、dp[1] 0——因为你可以免费站在第 0 阶或第 1 阶上。6.3 变形三输出所有爬楼方案而不是数量如果面试官问“你能把所有方案都打印出来吗”这就不是动态规划了而是回溯/DFS。状态转移的框架仍然可以用从 1 阶和 2 阶搭路径收集所有长度为 n 的路径。def climb_all(n: int): res [] def backtrack(cur, path): if cur n: res.append(path[:]) return if cur 1 n: backtrack(cur 1, path [1]) if cur 2 n: backtrack(cur 2, path [2]) backtrack(0, []) return res这种追问在面试中很常见主要考察你能不能从“计数”切换到“枚举”并且意识到两者的复杂度天差地别计数可以 O(n)枚举因为结果本身就是指数级的永远快不了。6.4 想清楚这题能“套模板”吗网上流传的“动态规划五步法”即使背得再熟也要结合题意。70 题的“套模板”很容易定义数组、找转移、定初值、写循环。真正拉开差距的是最后一步——你说不清为什么转移方程长这样。所以每次刷到 Hot 100 里的递推题我都要求自己先口头解释一遍“最后一步逻辑”再动手写代码。这个习惯成本很低但收获极大。7. 实测中的坑与自查清单7.1 整数溢出是一个真实的坑LeetCode 原题返回 int而 f(45) 1836311903刚好没有超过 int 上限 2147483647这是出题人刻意为之的边界。但如果你把同样的代码提交到别的 OJn 改成 46C 的 int 就直接溢出了返回一个负数你会调试到怀疑人生。所以我的建议是不管题目给没给范围只要是递推求数值的题默认用 long longC、longJava或者 Python 的大整数。反正 Python 没有溢出问题但 Java 和 C 必须警醒。7.2 递归深度的边界问题记忆化搜索虽然写着方便但递归深度是硬约束。如果你用 Python默认递归限制是 1000 层可以通过 sys.setrecursionlimit 调大但默认别依赖。所以在 n 比较大的题目上别用递归写法去赌。面试时选择自底向上的循环不仅能避开这个坑还显得你更老练。7.3 提交前跑一遍边界测试我在刷题插件里给自己定了一条铁律写完代码先跑 n1、n2、n3 三个用例再跑一个中等值和一个大值。虽然很简单但能过滤掉 80% 的边界错误。比如很多人把 dp 数组开成n而不是n1然后访问dp[n]时报数组越界还有人把if n 2: return 2这种逻辑漏掉导致 n1 返回 2。拿这道题实测我建议至少验证三组n1人工答案 1n2人工答案 2n3人工答案 3n45应该输出 1836311903最后一个数字我全靠经验记忆1836311903。写错一个数立刻能发现。7.4 从刷题到工程思维的迁移最后说点实在的。有人问爬楼梯这种题除了面试到底有什么用我后来在业务里接触过爬虫的调度路径计数、前端的路由层级方案枚举、甚至 CI 流程里步骤组合的可行性判断底层思路都有影子。真实项目不会把题目原封不动搬过来但“把大问题拆成最后一步加前面子问题”的思维模型是能复用一辈子的。我自己在第二遍刷 Hot 100 的时候把每道简单题都强迫自己多想一步。比如这题我会额外问自己如果允许相邻两步不能都爬 2 阶怎么改如果每步能爬的阶数是一个数组[1,2,4]状态转移又怎么写这些延伸训练能让你在面试中遇到任何变体都不慌因为你已经把底层逻辑吃透了。爬楼梯这道题就像算法领域的“举重入门”练好了后面的硬拉和挺举才有基础。