刷LeetCode Hot100这段时间进度卡到了64/100刚刚把第70题“爬楼梯”AC掉。这道题在Hot100里排得挺靠前属于动态规划入门必刷题面试出现的频率也高。有意思的是很多人第一次看这道题觉得太简单了不就是斐波那契吗可真要讲清楚“为什么dp[3] dp[1] dp[2]”能当场说明白的人不多。我借着Hot100刷题记录把这题从暴力递归到动态规划再到矩阵快速幂完整拆一遍顺带把实际提交中踩过的坑、常见的变体题一并梳理出来。不管是刚开始刷Hot100的新手还是想查漏补缺的老手这篇都能给你点实在的东西。先从题目本身说起。LeetCode 70. 爬楼梯题目描述很直接假设你正在爬楼梯需要 n 阶才能到达楼顶每次可以爬 1 或 2 个台阶有多少种不同的方法可以爬到楼顶注意n 是一个正整数样例里 n 2 输出 2n 3 输出 3。很多人第一眼看到这个题目会觉得“这不就是高中数学里的斐波那契数列吗”确实但题目考察的不只是背公式而是你能不能从问题中抽象出状态转移关系这恰恰是动态规划的核心能力。1. 先看题爬楼梯到底在问什么1.1 题目描述与示例题目输入一个正整数 n输出爬到第 n 阶的方案总数。给两个官方示例n 2有两种方法1 阶 1 阶或者 2 阶直接输出 2。n 3有三种方法111、12、21输出 3。注意看n 3 里的“12”和“21”是两种不同方案因为走的顺序不同分别对应先迈 1 阶再迈 2 阶以及先迈 2 阶再迈 1 阶。这个细节很关键很多人列方案时会漏掉“顺序不同算不同”这个约束导致样例都对不上。题目还给了隐含参数范围n 最大到 45。这个范围很有讲究。如果 n 上限是 10^9那这题就不是简单动态规划能搞定的得考虑矩阵快速幂或通项公式上限定在 45意味着普通 O(n) 的解法完全够用LeetCode 故意把难度控制在“动态规划入门”这个档位。刷 Hot100 时要注意题目的数据范围往往暗示了期望解法这也是面试中判断候选人能不能“读懂题目”的重要信号。1.2 这题为什么能进 Hot100Hot100 是 LeetCode 上被收藏、被考察次数最多的 100 道题能进去的题一般具备两个特点考察核心算法思想且能在一道题里延伸出多个变形题。爬楼梯完美符合这两个条件。它表面是计数问题本质是“斐波那契数列”的应用而斐波那契这个模型在算法题里太常用了——上台阶、铺地砖、兔子繁殖、跳格子全都是同一套状态转移逻辑。另一个原因是它足够简单适合作为动态规划的第一课。动态规划最劝退新手的点是“为什么能这样拆”爬楼梯把这个过程变得很直观你站在第 n 阶往前看最后一步要么是从 n-1 迈 1 阶上来要么从 n-2 迈 2 阶上来所以到达第 n 阶的方法数等于到达 n-1 阶的方法数加上到达 n-2 阶的方法数。这个推导没有任何弯弯绕绕但恰恰是动态规划里“状态定义 转移方程”的完整演示。把爬楼梯吃透再看打家劫舍、不同路径、零钱兑换这些题状态定义就自然有感觉了。1.3 输入规模与复杂度预期在动手写代码前先算一笔复杂度账。n 最大 45递归暴力的时间复杂度大约是 O(2^n)n 45 时大约是 3.5 万亿次运算绝无可能跑完动态规划 O(n) 时间n 45 时 45 次循环毫秒级完成如果上矩阵快速幂O(log n) 时间对 n 45 来说是杀鸡用牛刀但 n 放大到 10^18 也能扛住。空间复杂度方面最朴素的 dp 数组是 O(n)滚动数组可以优化到 O(1)。面试时通常要求给出“时间 O(n)、空间 O(1)”的解法这也是最优解的基本盘。我在 Hot100 刷题时有个习惯每道题先看数据范围再定复杂度目标这一步能帮你避免写出“能过但不是最优”的代码。2. 递归解法直觉没错但别急着提交2.1 f(n) f(n-1) f(n-2) 是怎么推出来的回到问题本身。要求到达第 n 阶的方案数假设这个数是 f(n)。考虑你到达第 n 阶之前的那一步也就是最后一步。因为每次只能走 1 阶或 2 阶所以最后一步只有两种可能从第 n-1 阶走 1 阶上来。这种情况下前面 n-1 阶有多少种走法整体就有多少种走法因为最后一步已经被固定住了所以贡献是 f(n-1)。从第 n-2 阶走 2 阶上来。同理最后一步固定前面 n-2 阶的走法数就是整体贡献所以贡献是 f(n-2)。两种情形互斥不存在既从 n-1 又从 n-2 跳上来的情况所以总数直接相加f(n) f(n-1) f(n-2)。边界条件是 f(1) 11 个台阶只有 1 种走法f(2) 211 或 2。这里有一个很容易忽略的点为什么不需要考虑“从 n-2 走 1 阶到 n-1再走 1 阶到 n”这种拆法因为这种情况已经被包含在“最后一步从 n-1 走 1 阶”里了n-1 阶的走法里面本来就包含了从 n-2 走 1 阶上来的路径。换句话说状态转移只盯着“最后一步”前面的中间过程全部交给子问题去处理这就是动态规划“无后效性”的直观体现。2.2 指数爆炸递归为什么会超时按照 f(n) f(n-1) f(n-2) 直接写递归代码很简短def climbStairs(n: int) - int: if n 1: return 1 if n 2: return 2 return climbStairs(n - 1) climbStairs(n - 2)这段代码逻辑完全正确但提交会超时。原因是指数级的时间复杂度。我们来看递归的调用过程算 f(5) 需要算 f(4) 和 f(3)算 f(4) 又需要算 f(3) 和 f(2)这个 f(3) 被重复计算了两次。往下展开f(2) 会被调用无数次。整个递归树是一棵近似完全二叉树节点数接近 2^n。我用 n 45 实测了一下在我这台机器上纯递归版跑了几分钟也没出来直接放弃。n 30 的时候大概需要 1 秒出头n 40 已经是 30 秒以上。读者可以自己在本地跑 n 30 感受一下那个卡顿这是理解“重复计算是动态规划要解决的核心问题”的绝佳体验。面试时如果只写出递归版面试官基本会追问“时间复杂度多少有没有改进空间”答不上来就危险了。2.3 记忆化搜索加一个缓存复杂度立刻降下来既然问题出在重复计算那就在计算时把结果存起来下次直接用。这就是记忆化搜索也叫带缓存的递归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)这样改完每个 f(k) 只会被真正计算一次后续直接查表。时间复杂度从 O(2^n) 降到 O(n)因为每个 k 最多计算一次每次计算是常数时间空间复杂度 O(n)来自递归栈和 memo 表。记忆化搜索和动态规划本质上是一回事只是方向不同记忆化是自顶向下先想 f(n)递归时拆成子问题动态规划是自底向上先从 f(1)、f(2) 开始往上推。两者都用“子问题结果缓存”来避免重复计算区别只是编码习惯。对爬楼梯这种简单题记忆化搜索有点“大材小用”但它在状态转移不好直接写循环时特别好用比如区间 DP、树形 DP自顶向下写起来思路更清晰。我的建议是递归 记忆化可以作为打草稿的工具先验证状态转移对不对再改写成自底向上的迭代。3. 动态规划用迭代替代递归3.1 自底向上的 dp 数组写法递归虽然加缓存能过但有两个小问题一是递归栈深n 稍微大点可能栈溢出二是频繁函数调用有额外开销。更标准、也更推荐在面试里写的是自底向上的动态规划。定义 dp[i] 表示到达第 i 阶的方案数初始 dp[1] 1dp[2] 2然后从 3 循环到 n执行 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]这个版本的时间复杂度 O(n)空间复杂度 O(n)。dp 数组的下标从 1 到 n多开了一个 dp[0] 占位。很多新手纠结 dp[0] 应该初始化成什么这里我的建议是直接不处理 dp[0]从 dp[1] 开始循环也从 3 开始逻辑清晰不会把自己绕晕。至于 dp[0] 的语义其实是“到达第 0 阶的方案数是 1”站在原地不动算一种这在数学推导里有用但写代码时没必要纠结用“若 n 2 直接返回 n”来兜底更干脆。3.2 滚动数组把空间从 O(n) 压缩到 O(1)再进一步观察 dp[i] dp[i-1] dp[i-2]每一步只依赖前两个值。也就是说dp[3] 算完dp[1] 就再也不会被用到了dp[4] 算完dp[2] 也没用了。整个过程中真正需要保留的只有“上一个值”和“上上个值”那就没必要开一整条数组用两个变量滚动接力就行。def climbStairs(n: int) - int: if n 2: return n prev2, prev1 1, 2 # prev2 dp[1], prev1 dp[2] for i in range(3, n 1): cur prev1 prev2 prev2 prev1 prev1 cur return prev1这里有个容易绕的点循环里 cur 是当前 dp[i]算完之后要把 prev1旧的 dp[i-1]变成 prev2新的 dp[i-2]把 cur 变成新的 prev1新的 dp[i-1]所以代码里是先 prev2 prev1再 prev1 cur顺序不能反。最后循环结束时 prev1 就是 dp[n]直接返回。空间复杂度从 O(n) 降到 O(1)这一优化在面试里是“送分题”但很多人恰恰栽在“忘记了为什么能这么压缩”上面。我建议新手还是先把 dp 数组版本写熟理解了“只依赖前两个值”这个关键点再写滚动数组版本否则面试一紧张很容易把更新顺序写反。3.3 边界条件和初始化细节爬楼梯的边界条件看起来简单实际提交时很容易踩坑。第一n 的范围是正整数但有些平台测试用例可能给 n 0 甚至 n 1代码里必须考虑。我见过有人只写了 n 1 的边界结果 n 2 时数组越界。第二dp 数组版本中如果 n 1 且你还初始化了 dp[2]就需要先判断 n 2 直接返回否则访问 dp[2] 会越界。第三返回值可能超出 int 范围吗这里 n 最大 45f(45) 是 1836311903还在 int 范围内但如果你在扩展题里把 n 放大到 10^5就要考虑取模面试时最好主动提一句“如果 n 很大结果要取模”。我看过不少提交记录大部分错误都出在没处理 n 2 的边界或者滚动数组更新顺序写反。这两个问题都属于“逻辑简单但代码细节容易翻车”的类型写完后务必用 n 1、2、3、4 手算一遍核对结果30 秒的时间可以避免一次无谓的提交失败。4. 再说透一点爬楼梯的本质是斐波那契4.1 为什么说它和斐波那契是同族的经典的斐波那契数列定义是 F(1) 1, F(2) 1, F(n) F(n-1) F(n-2)得到 1, 1, 2, 3, 5, 8...。爬楼梯的数列是 f(1) 1, f(2) 2, f(n) f(n-1) f(n-2)得到 1, 2, 3, 5, 8...。两者就差一个初始值从 f(2) 开始爬楼梯数列就是斐波那契数列去掉最前面的 1。这也是为什么很多资料说爬楼梯就是斐波那契数列的“换皮”。理解这一点有啥用第一个用处是能立刻反应过来这类题可以套斐波那契的快速算法。第二个用处是帮你加深“初始条件决定数列形态”的认知很多动态规划题的转移方程看似相同但初始值不同结果完全不同。比如假设每次可以爬 1、2、3 阶转移方程就变成 f(n) f(n-1) f(n-2) f(n-3)初始条件也要相应调整。这都是同一套思路的延伸。4.2 矩阵快速幂给面试官一个惊喜但慎用斐波那契数列可以用矩阵快速幂在 O(log n) 时间内算出第 n 项爬楼梯同理。构造递推关系的矩阵形式[f(n)] [1 1] [f(n-1)] [f(n-1)] [1 0] * [f(n-2)]这样 f(n) 就等于矩阵 [[1,1],[1,0]] 的 n-2 次幂乘以初始向量 [f(2), f(1)]中间用快速幂计算矩阵乘法。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 power(matrix, k): res [[1, 0], [0, 1]] # 单位矩阵 while k: if k 1: res mul(res, matrix) matrix mul(matrix, matrix) k 1 return res mat power([[1, 1], [1, 0]], n - 2) return mat[0][0] * 2 mat[0][1] * 1说实话对这道题来说n 最大 45矩阵快速幂纯属炫技实操价值不大。但在面试中如果你能把“这题的递推本质是斐波那契如果 n 扩大到 10^18用矩阵快速幂能把时间压到 O(log n)”这句话讲清楚是很加分的。不过要提醒一点不要为了炫耀写这种解法面试官让你爬楼梯题基本是想看你动态规划基本功写矩阵快速幂容易显得“背模板”。4.3 通项公式可以直接算吗斐波那契有通项公式比奈公式f(n) ( (1√5)/2 )^(n1) / √5 - ( (1-√5)/2 )^(n1) / √5算出来是浮点数需要取整。爬楼梯的 f(n) 就是斐波那契的 F(n1)所以理论上直接套公式再加个 round 就行。但实际刷题时不建议用原因是浮点数有精度误差n 一大人就会出错。LeetCode 的题目不会设计到需要你用通项公式的程度但如果你在系统设计里遇到“计算第 n 个斐波那契数”这种高频调用场景通项公式和矩阵快速幂是两种典型的优化手段理解原理即可。5. 实战记录从 TLE 到 AC 的完整过程5.1 我第一次提交的代码和超时记录我最初提交的就是最朴素的递归版本当时心想这题这么简单直接交上去就完事了。结果 LeetCode 直接给了个“Time Limit Exceeded”。我当时是用 n 44 的用例眼睁睁看着递归树疯狂展开。这里给一个直观的数据纯递归计算 f(40) 需要调用 climbStairs 函数约 3.3 亿次单次调用虽便宜但这个量级在在线判题环境里是铁定超时的。那次 TLE 给我提了个醒越是看起来简单的题越要先想清楚复杂度再动手写代码。5.2 最终的 AC 版本长什么样我最终提交的版本就是前面写的滚动数组版并且加了两行边界处理。完整代码如下class Solution: def climbStairs(self, n: int) - int: if n 2: return n prev2, prev1 1, 2 for _ in range(3, n 1): cur prev1 prev2 prev2 prev1 prev1 cur return prev1运行时间大概 20ms 出头内存占用 13MB 左右击败了相当比例的提交。这里我比较满意的是代码够短、逻辑直接面试时手写这种版本最稳。不过需要注意LeetCode 的“击败百分比”受提交版本和用例影响很大没必要为了那点百分比把代码写成花正确性永远是第一位的。5.3 边界测试和踩坑清单我在本地跑了几组边界测试输入 n预期结果实际输出说明111最小区间走了 n 2 分支222第二种初始边界333首次进入循环的用例108989循环多次验证滚动更新4518363119031836311903最大值验证 int 不越界踩坑记录里排名第一的是“dp 数组越界”——如果你没在最前面加 n 2 的判断当 n 1 时访问 dp[2] 就会崩。排名第二的是滚动数组更新顺序搞反写过一次 prev1 cur 之后再执行 prev2 prev1结果把刚更新完的 cur 当成旧值赋给了 prev2整个数列全错。这个 bug 很难肉眼发现因为 n 小的时候算出来恰好是菲波那契的某一项你会以为自己是写对了直到 n 5 输出 7 而不是 8 才反应过来。还有一个不是错误但是我强烈建议的做法拿到题目先手推 n 4 或 n 5 的完整走法明确答案后再写代码。很多所谓“边界条件没考虑好”实际上是连答案都没算对就开始写了自然会在细节上翻车。6. 变体题怎么打爬楼梯的常见变形6.1 一次能爬 1~k 阶第一个变体每次可以爬 1 到 k 阶楼梯比如 1、2、3 阶问爬到 n 阶有多少种方法。转移方程变成 f(n) f(n-1) f(n-2) ... f(n-k)。写代码时可以用一个长度为 k 的滑动窗口或者更通用的先算前缀和然后用前缀和加速。def climbStairs_k(n: int, k: int) - int: dp [0] * (n 1) dp[0] 1 for i in range(1, n 1): for step in range(1, k 1): if i - step 0: dp[i] dp[i - step] return dp[n]这里 dp[0] 1 就派上用场了它表示“站在起点算一种方案”和之前 dp 数组版本里刻意回避 dp[0] 不同这种写法下 dp[0] 是必需的。如果 k 很大内层循环是 O(nk)可以在循环里维护窗口和优化到 O(n)。6.2 带体力代价的爬楼梯第二个常见变形是给每级台阶一个体力值 cost[i]你每次可以选择爬 1 级或 2 级但踩到哪级就要付哪级的 cost问爬到楼顶的最小花费。这题在 LeetCode 上是 746 题“使用最小花费爬楼梯”也进了 Hot100。转移方程是 dp[i] min(dp[i-1], dp[i-2]) cost[i]表示到达第 i 级的最小花费等于从第 i-1 级或 i-2 级跳上来的花费加上本级的体力值。最后答案要从 dp[n-1] 和 dp[n-2] 里再取一个 min因为可以从最后两级中的任意一级直接跳出去。这个变体和爬楼梯放一起练特别好一个是加法求和一个是 min 取最优状态定义和转移逻辑完全一脉相承但考察点从“计数”变成了“最优化”。很多人说动态规划入门进阶的关键就是从“求方案数”到“求最优值”这两道题正好构成这个跳跃的阶梯。6.3 有障碍物的版本再一个变体是“不同路径”系列比如二维网格里从左上角到右下角有多少条路径有障碍物时怎么处理。这类题的状态定义从 dp[i] 变成 dp[i][j]转移关系从“只能往一个方向”扩展成“往右或往下”但核心思路还是“当前位置的方案数等于能到达它的前置位置方案数之和”。我现在刷 Hot100 到 64 题明显能感觉到“不同路径”、“打家劫舍”、“零钱兑换”这些题和爬楼梯都是同一个妈生的状态定义方式几乎可以平移。6.4 Hot100 里同类型的基础题速查这段时间在 Hot100 里刷下来发现和爬楼梯强相关的题不少整理了一个速查表方便大家按顺序刷题号题目与爬楼梯的关联70爬楼梯最基础的线性 DP转移方程 f(n)f(n-1)f(n-2)198打家劫舍同样是一维 DP但状态转移多一个“相邻不能同时选”的约束746使用最小花费爬楼梯等价于带权重的爬楼梯需求从计数变成最优解62不同路径一维扩展成二维计数思想一致63不同路径 II加障碍物的计数变体322零钱兑换状态维度从“台阶数”变成“金额”但都是自底向上建立 dp 表另外Hot100 里还有一道 073 题“爱吃香蕉的狒狒”虽然主题是二分搜索不是动态规划但它的套路也是“单调性 检查函数”和爬楼梯里“递推关系 边界条件”一样都是面试官爱考的基础模型。刷 Hot100 不用死磕顺序把同类题型放在一起集中刷效率比零散刷高得多。我个人习惯是每道题刷完顺手记录一下状态定义、转移方程、边界条件这三件套。爬楼梯的三件套是dp[i] 表示到达第 i 阶的方案数dp[i] dp[i-1] dp[i-2]dp[1] 1, dp[2] 2。等你刷到第 40 题、第 60 题时会发现所有动态规划题都是在给这三个要素填空区别只是填的内容越来越复杂。最后说点实在的经验。这段时间在 Hot100 上刷到 64/100最大的体会是动态规划大题不要一上来就想最优解而是先写一个能跑的递归再想怎么优化。爬楼梯这道题把“递归 TLE - 记忆化搜索 - 动态规划 - 滚动数组”的演进路线完整走了一遍花了不到二十分钟但这套流程给我带来的收益远超二十分钟。面试时你甚至可以从递归讲起主动演示优化过程这比直接甩一个滚动数组版代码更有说服力因为面试官想看的不是你背过答案而是你具备从暴力到优化的思维链条。一个小技巧收尾下次遇到任何一维 dp 题强行让自己先写递归版本再套记忆化再转迭代——这套肌肉记忆建立起来之后Hot100 后半程的速度会明显快起来。爬楼梯只是起点动态规划的天花板高得很但地基在这里。