LeetCode 70 爬楼梯：动态规划入门与滚动数组优化详解

1. 题目分析与核心思路LeetCode 热题 HOT 100 里的第 70 题“爬楼梯”是一道看起来简单、实际上非常经典的入门级动态规划题目。我刷题这么多年见过无数人卡在这道题上——不是不会写代码而是没有想明白“为什么这么写”。如果你把这道题吃透了后面遇到一大票动态规划题目都会有底气得多比如打家劫舍、斐波那契数、跳跃游戏系列骨子里的套路是相通的。先看题目本身假设你正在爬楼梯需要 n 阶才能到达楼顶每次你可以爬 1 或 2 个台阶问有多少种不同的方法可以爬到楼顶。我第一次做这道题的时候第一反应是暴力搜索直接递归枚举所有可能性。后来发现数据范围稍微大一点就超时了这才开始认真琢磨它背后的递推关系。1.1 题目拆解与递推关系我们要想清楚一个问题到达第 n 阶楼梯最后一步是怎么走的只有两种可能从第 n-1 阶爬 1 个台阶上来从第 n-2 阶爬 2 个台阶上来也就是说到达第 n 阶的方法总数等于到达第 n-1 阶的方法总数加上到达第 n-2 阶的方法总数。这就是标准的斐波那契数列递推式设 dp[i] 表示爬到第 i 阶的方法数那么dp[i] dp[i-1] dp[i-2]边界条件也很直观第 1 阶只有 1 种方法直接爬 1 步第 2 阶有 2 种方法11 或者一次爬 2 步。这里我想多说一句很多教程把边界条件写成 dp[0] 1 和 dp[1] 1。两种写法都能 AC但含义略有不同。dp[0] 1 是一种偏数学化的处理为了统一递推公式而 dp[1] 1、dp[2] 2 更贴近实际场景对初学者来说更好理解。我个人建议用后者不容易绕晕。1.2 为什么它值得进 HOT 100这道题不只是简单的递推它几乎涵盖了入门动态规划的所有关键点状态定义、状态转移方程、边界初始化、空间优化。而且在面试里面试官特别喜欢拿这道题考察候选人因为你可以从这个题目一路追问到滚动数组、矩阵快速幂、通项公式能快速判断一个人对算法理解的深度。有个很现实的情况是很多人背住了代码但换个问法就懵了。比如面试官问“如果每次可以爬 1、2、3 阶怎么写”或者“如果某些台阶是坏的不能踩怎么写”这时候如果没有真正理解状态转移的本质就很难答好。所以这篇文章我不打算只贴一个标准答案而是把从暴力递归到动态规划再到进阶解法的完整推导链讲清楚顺便聊聊实际面试中可能出现的变形题和刷题时的避坑心得。2. 四种主流解法逐个拆解我见过不少人在力扣评论区争论“滚动数组到底是不是动态规划”也见过有人上来就直接背“斐波那契数列套公式”。这些讨论本身没毛病但容易让新手偏离主线。我的建议是按难度递进的顺序来学每一步都搞明白然后再决定用哪种方案去写。2.1 暴力递归先把问题想明白第一版我写的是最朴素的递归def climbStairs(n: int) - int: if n 1: return 1 if n 2: return 2 return climbStairs(n - 1) climbStairs(n - 2)这段代码逻辑完全正确但跑 n 45 的时候耗时已经到几十秒级别。原因在于它把大量重复的子问题算了一遍又一遍。比如计算 climbStairs(10) 的时候会递归去算 climbStairs(9) 和 climbStairs(8)而 climbStairs(9) 又会去算 climbStairs(8)同一件事重复做了很多次。这就像你每天把同一份表格填十遍效率当然低。递归树展开之后时间复杂度是 O(2^n)空间复杂度是递归栈深度 O(n)。说实话看递归代码理解题意非常舒服但实战千万别这么写。很多刚开始刷题的朋友容易陷入一个误区做出来了就不管复杂度了。LeetCode 上有个隐藏的测试数据范围n 最大能到 45暴力递归在这个范围内已经比较吃力了。要学会主动思考“这个方案能不能更好”。2.2 记忆化搜索给递归加一个缓存既然递归慢是因为重复计算那就把算过的结果存起来。用一个字典或者数组做缓存每次递归前先查表def climbStairs(n: int) - int: memo {1: 1, 2: 2} def dfs(k): if k in memo: return memo[k] memo[k] dfs(k - 1) dfs(k - 2) return memo[k] return dfs(n)这种“自顶向下 缓存”的方式称为记忆化搜索时间复杂度降到了 O(n)空间复杂度 O(n)。它和动态规划的差别只是计算顺序不同一个从大往小递归一个从小往大递推。理解记忆化搜索很重要因为很多复杂的动态规划题目比如树形 DP、区间 DP用自顶向下的写法反而更容易想通。我个人的经验是遇到没见过的 DP 题先用记忆化搜索把暴力解改成高效解能跑过测试了再根据情况改写成自底向上的迭代版本。两步走不容易出错尤其是面试现场紧张的时候这个策略特别稳妥。2.3 动态规划标准递推写法自底向上的版本就是前面提到的递推公式直接开一个长度为 n1 的数组def climbStairs(n: int) - int: if n 1: return 1 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]dp 数组下标从 0 到 ndp[i] 表示爬到第 i 阶的方法数。为什么数组长度是 n1因为我们要用到下标 nPython 下标从 0 开始所以长度为 n1 才能访问到 dp[n]。这里有一个细节值得注意如果你初始化了 dp[0]那就必须问自己 dp[0] 代表了什么。从实际意义出发第 0 阶是地面一种“站在地上不动”的方案所以 dp[0] 1 的解释也说得通只是不如 dp[1] 1 来得直观。这种写法的时间和空间复杂度都是 O(n)。在数据规模 n ≤ 45 的 LeetCode 原题里已经绰绰有余。我见过不少人在写这题的时候栽在边界的细节上比如 n 0 时直接返回 dp[0]或者 n 1 时循环体压根不跑但 dp[1] 已经被赋值了。这些都是小坑写之前先想清楚边界就能避免。2.4 滚动数组优化空间压缩到常数级观察递推式 dp[i] dp[i-1] dp[i-2]你会发现计算当前状态只需要用到前两个状态更早的数据完全没用。所以没必要保留整个 dp 数组只保留三个变量就够了def climbStairs(n: int) - int: if n 1: return 1 prev, curr 1, 2 for i in range(3, n 1): prev, curr curr, prev curr return curr初始时 prev 1 对应 dp[1]curr 2 对应 dp[2]。循环从 3 到 n每次把 prev 更新为旧的 currcurr 更新为两者的和。循环结束后 curr 就是 dp[n]。这个操作的原理是状态转移只依赖于前两个状态所以可以用“滚动”的方式复用变量。时间和空间都优化到 O(1) 空间时间复杂度保持 O(n)。这里有个初学者容易懵的地方Python 的prev, curr curr, prev curr是先计算右边再统一赋值的所以不会出现值被覆盖的问题。如果你用其他语言写就得用一个临时变量暂存旧值否则会有赋值顺序导致的逻辑 bug。我在面试里见过好几个候选人栽在这个细节上写 Java 或 C 的时候忽略了暂存结果怎么跑答案都是错的。3. 进阶解法与数学原理如果你只是想把 LeetCode 第 70 题 AC 掉上面四种方案已经足够了。但这道题的魅力在于它是个“套了马甲的斐波那契数列”深入研究下去还能接触到很多漂亮的解法。3.1 矩阵快速幂思路斐波那契数列有一种经典加速方法矩阵快速幂。把递推公式转换成矩阵形式[dp[i], dp[i-1]] 的转移可以写成[dp[i] ] [1 1] [dp[i-1]] [dp[i-1]] [1 0] [dp[i-2]]于是从 dp[1], dp[2] 出发计算 n-2 次矩阵乘法就能得到 dp[n]。快速幂可以把矩阵幂运算从 O(n) 降到 O(log n)n 非常大的时候优势就体现出来了。实际工程中 n 通常小意义不大但算法竞赛和大数场景下矩阵快速幂是很多题目的必备技能。有兴趣的朋友可以自己实现一遍加深对“状态转移矩阵”的理解。3.2 通项公式解法斐波那契数列还有精确的闭式解也就是贝特朗-切比雪夫公式Binet 公式。对爬楼梯问题来说结果等于一个包含黄金比例的表达式dp[n] ( ((1√5)/2)^(n1) - ((1-√5)/2)^(n1) ) / √5直接用这个公式算对 n 特别大的时候需要用到浮点运算和高精度技巧处理不好会损失精度。所以LeetCode 场景下我不推荐但理解这个公式能帮助你串联起算法和数学的联系。以后遇到“求斐波那契数的后几位”这类题目你就会有额外的手段矩阵快速幂 模运算可以应对。这里要提一句如果面试官问你“有没有 O(log n) 的方案”矩阵快速幂是最稳妥的回答通项公式虽然理论上也行但实现起来容易在精度上翻车不是每个人都驾驭得了。3.3 三种方案怎么选直接给个结论方便你按场景决策方案时间复杂度空间复杂度适用场景暴力递归O(2^n)O(n)仅用于理解题意记忆化搜索O(n)O(n)自顶向下思维的入门练习动态规划数组O(n)O(n)最稳妥的面试答案滚动数组O(n)O(1)面试加分项工程中最实用矩阵快速幂O(log n)O(1)竞赛场景或 n 极大时刷题阶段我认为最值得掌握的方案是滚动数组代码量少、思路清晰、还能顺手展示你对空间复杂度的敏感性。很多人以为面试题写出 O(n) 空间就够了实际上“能不能优化”往往是区分普通候选人和优秀候选人的分水岭。4. 题目变形与工程场景联想学会一道题不算本事能把它迁移到别的场景才算真正掌握。爬楼梯类型的问题在现实里其实有大量变体面试官也格外喜欢在变体上做文章。4.1 常见的变形题变形一每次可以爬 1 或 2 或 3 个台阶。递推式变成 dp[i] dp[i-1] dp[i-2] dp[i-3]初始条件需要好好推。dp[1] 1dp[2] 2dp[3] 4111、12、21、3。从 i 4 开始套递推就可以。变形二某几阶台阶是破损的不能踩。这种题本质上是“带障碍物的路径计数”状态转移时把不能走的台阶对应 dp 值设为 0 即可。比如 dp[i] 0 if broken else dp[i-1] dp[i-2]。变形三要求不能连续爬两次 2 阶。这就不是一维 DP 能搞定的了需要加一个状态维度来记录“上一次操作是什么”变成二维 DP。我在面试中被问到过当时第一反应是一维 DP结果走了弯路后来才意识到状态不够用的时候就应该加维度。变形四如果每一步可以选择 1 或 2但要付出不同体力值求最小消耗。这就是 LeetCode 746 题“使用最小花费爬楼梯”的原型属于动态规划里的“最短路”思想。思路换成 dp[i] min(dp[i-1], dp[i-2]) cost[i]本质上和爬楼梯是同源问题。4.2 工程中的实际类比你可能觉得爬楼梯只存在于算法题里其实它在真实业务中也不少。举个例子路由跳转的步数计算、Excel 表格中从单元格 A 到 B 的移动方案数、产品运营里“用户每日步数选择叠加达到目标值”的组合数统计都可以抽象成类似的递推模型。我几年前在做一个营销活动需求时就遇到过类似的计数问题用户每天签到有 1 积分或 2 积分两种奖励问第 n 天累计积分刚好等于某个值有多少种组合。本质上就是爬楼梯的变体。当时我把递推公式写清楚之后后端用滚动数组实现了 O(1) 空间的计数逻辑线上抗住了高峰期流量。从那以后我对这道题有了不一样的感情——它不只是面试题也是日常编码里抽象建模的好素材。5. 刷题避坑指南与学习方法刷 LeetCode HOT 100 的顺序其实很有讲究。很多新人按题号从 1 开始刷刷到链表和哈希表就坚持不下去了。我的观点是按类型刷比按题号刷更高效。爬楼梯属于“一维动态规划”类型的入门题建议把它排在 DP 专题的第一个和斐波那契数509、使用最小花费爬楼梯746放在一起做对比练习。5.1 刷这题最常见的三个坑第一个坑不写边界条件。n 1 和 n 2 的时候某些代码会直接越界或者返回错误结果。尤其是用 dp 数组的版本如果你把 dp[1] 和 dp[2] 都初始化了n 1 时循环不执行但返回 dp[1] 是没问题的可如果你漏了 n 1 的提前返回访问 dp[2] 就会越界。这个细节在 C/C 里特别致命Python 里则会报 IndexError。第二个坑把斐波那契数列的下标对应错。LeetCode 爬楼梯第 n 阶对应斐波那契数列的 F(n1)因为爬楼梯序列是 1, 2, 3, 5, 8...而斐波那契是 1, 1, 2, 3, 5, 8...。如果你直接用斐波那契的公式搞错一位就是错答案。写之前先在纸上列几个小值对照一下至少我吃过这个亏印象特别深。第三个坑状态定义不清晰。有些解法把 dp[i] 定义成“恰好还有 i 阶要爬”的方案数从尾部往前推有的把 dp[i] 定义成“从第 0 阶爬到第 i 阶”的方案数。两种都能写对但混在一起容易头晕。我的建议是统一用“从起点爬到第 i 阶”的语义从头往后推思路最自然也不容易出错。5.2 如何举一反三地练 DP爬楼梯这道题吃透之后我建议你用同样的方法尝试以下节奏每天做一道“一维 DP”题持续一周重点练习从暴力递归到滚动数组的优化链路。每周挑一天把本周做过的题重新用“记忆化搜索 迭代 DP 滚动数组”三种方案各写一遍加深对状态转移的肌肉记忆。试着给做过的每一道 DP 题写一个“变形问题”像我在第四部分做的那样。能给别人出一道题说明你真的掌握了这道题。我记得自己刚开始刷 DP 题的时候遇到不会的题第一反应是看题解、抄答案、粘代码。后来发现抄十道不如自己推两道。把递推公式自己在纸上推一遍把边界条件列出来哪怕最后代码写得慢一点收获也远大于直接抄。5.3 面试时的表演技巧面试中如果被问到爬楼梯不要急着背答案先和面试官确认约束条件。比如 n 的范围是多少是否要求空间 O(1)是否允许数学公式解。这既能体现你的交流能力又能帮你争取一点思考时间还能避免方案选型失误。我面试别人的时候特别看重候选人会不会主动确认输入范围和边界约束而不是闷头就写。写代码的时候可以边写边说。比如写到初始化条件时解释一下“dp[1] 1 表示爬 1 阶只有一种方法dp[2] 2 表示爬 2 阶有两种方法”。这不仅让面试官跟上你的思路也能保证你自己不会乱。写完代码后主动说一句“这段代码可以通过滚动数组优化空间复杂度到 O(1)”往往是一个不错的加分项。6. 最后一道变式题练手帮你加练一道题是爬楼梯的“加强版”也是我自己在面试中真实遇到过的题目给定 n 阶楼梯每次可以爬 1 或 2 阶但要求最后一步必须踏在第 n-1 阶上也就是不能从第 n-2 阶直接跨到第 n 阶求方案总数。这个限制条件其实排除了“最后两步是跨 2 阶”的情况因为如果最后一步从 n-2 直接到 n就没踏过 n-1。所以答案等于爬到第 n-1 阶的所有方案数也就是 dp[n-1]。你看想明白之后问题反而变简单了。如果面试官继续追加限制必须恰好连续爬两次 2 阶怎么处理这就需要增加维度了用二维 DP 记录已连续爬 2 阶的次数。我在这里不展开写代码了留给你自己思考。能把这个问题独立想清楚的动态规划的境界就上一个台阶。我在刷题这件事上踩过的最大坑就是求快。每道题看一眼题解觉得“哦原来这样”马上跳到下一道。这种假性掌握特别容易考前翻车。现在我的做法是同类型的题集中刷每道题至少自己先想 20 分钟想不出来再看题解并且看完题解后关掉答案重写。爬楼梯是动态规划家族里最温柔的入门题从那道题里养成的“推状态转移、找边界、优化空间”的习惯让我后面啃背包问题、区间 DP 的时候省了太多力气。这道仅有几行代码的简单题真的是刷题路上最值得反复咀嚼的一块基石。