LeetCode Hot100 刷到第64题遇到了一道几乎所有人都说自己会做的题70. 爬楼梯。题目本身短到只有两句话示例数据也小到不用动脑子——n3答案是3。但我还是把它单独拎出来写原因是这道题在 Hot100 里的位置太有代表性了它横跨递归、动态规划、组合数学和矩阵快速幂四个层次是把入门题吃成进阶题的最佳样本。如果你也在刷 Hot100可能和我一样前面几十道题已经见了各种二叉树、链表、滑动窗口突然来一道这么简单的爬楼梯反而会犹豫这题真的需要总结吗我的体会是真正需要记录的不是题目本身而是这道题背后的一整条优化链路。从暴力递归到记忆化从动态规划到滚动数组再到矩阵快速幂每一步都能讲出不少细节。这篇文章就按我复盘时的思路完整拆一遍。1. 爬楼梯这道题为什么值得被放进 Hot1001.1 题目在说什么题目背景很生活化你正在爬楼梯需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶问有多少种不同的方法可以爬到楼顶。示例也直观n 2答案是 21 阶 1 阶或者直接跨 2 阶。n 3答案是 3111、12、21。我第一次读题时的反应是这不就是斐波那契吗确实从结果上看它和斐波那契数列高度重合但如果你只满足于斐波那契四个字就会错过这道题真正的教学价值。LeetCode 上这道题的约束是1 n 45数值很小哪怕用 O(2^n) 的暴力递归n45 也已经会卡到怀疑人生但用动态规划只需要 O(n) 时间甚至 O(1) 空间就能跑完。这种明明数据小但解法复杂度天差地别的题目最适合用来训练算法思维。1.2 简单题背后的三种能力考察我复盘 Hot100 时发现能进 Hot100 的题目不一定难但一定有代表性。爬楼梯代表的是三类能力第一建模能力。看到方法数三个字要能想到从最后一步往前拆到达第 n 阶要么从第 n-1 阶跨 1 阶上来要么从第 n-2 阶跨 2 阶上来。于是问题被拆成两个规模更小的子问题。这种最后一步倒推的思维是几乎所有线性 DP 的起点。第二复杂度意识。递归写法最容易写但指数级复杂度在实际运行中完全不可接受。你需要知道重复子问题在哪里为什么缓存能解决问题为什么自底向上循环比递归更稳。第三知识迁移能力。爬楼梯的递推式是f(n) f(n-1) f(n-2)这不仅是斐波那契还能用组合数学直接计算甚至能用矩阵快速幂在 O(log n) 时间内解决超大 n。能把同一道题串出这么多解法本身就是面试中很加分的展示。下面我按自己刷题时的推进顺序从最暴力的递归开始一步步优化。2. 先走弯路递归版与指数爆炸2.1 最直觉的写法很多第一次接触这道题的人第一反应都是写递归def climbStairs(n): if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这个写法的依据非常朴素想要到达第 n 阶最后一步只有两种可能从 n-1 跨 1 阶或者从 n-2 跨 2 阶。所以到达第 n 阶的方法数等于到达第 n-1 阶的方法数加上到达第 n-2 阶的方法数。代码只有三行逻辑也正确。但如果你直接拿它去跑 LeetCoden 稍微大一点就会超时。因为这里面有大量重复计算。2.2 递归树里藏着复杂度真相我们可以把climbStairs(5)的递归调用展开成一棵树climbStairs(5) ├── climbStairs(4) │ ├── climbStairs(3) │ │ ├── climbStairs(2) 2 │ │ └── climbStairs(1) 1 │ └── climbStairs(2) 2 └── climbStairs(3) ├── climbStairs(2) 2 └── climbStairs(1) 1一眼就能看出来climbStairs(3)被算了两次climbStairs(2)被算了三次。n 越大这种重复子问题呈指数级增长。严格一点分析设 T(n) 表示递归函数处理 n 阶时执行的次数则有T(n) T(n-1) T(n-2) O(1)这个递推式的解是指数级的约等于 O(2^n)。虽然 n45 不是天文数字但指数级增长下重复计算的次数会膨胀到完全无法承受。这也是为什么递归写法虽然正确却不实用的根本原因。2.3 记忆化把重复计算缓存下来既然慢在重复计算那就把已经算过的结果存起来。记忆化搜索就是在递归的基础上加一个缓存def climbStairs(n): memo {} def dfs(i): 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)这样每个i只会被真正计算一次时间复杂度降到 O(n)空间复杂度 O(n)。递归深度也不会超过 45Python 默认递归深度足够。从暴力递归到记忆化搜索这一步能很自然地引出动态规划既然所有子问题都已经只计算一次那我为什么不能直接从小到大算一遍呢这就进入正解了。3. 动态规划的正解状态转移与滚动数组3.1 状态定义从递归返回反推我在面试中比较喜欢的讲法是不要凭空背状态定义而是从递归函数的返回值去反推。递归函数dfs(i)返回的是爬到第 i 阶的方法数所以动态规划的状态也很自然dp[i]表示爬到第 i 阶的方法数。转移方程就是递归体的镜像dp[i] dp[i-1] dp[i-2]初始条件有两种写法。主流写法是dp[1] 1dp[2] 2还有一种写法是把 dp[0] 设为 1这样 dp[2] dp[1] dp[0] 1 1 2 也能自洽。我个人更推荐显式初始化 dp[1] 和 dp[2]语义更清楚不容易误导初学者。3.2 循环递推代码使用数组保存全部状态的版本长这样def climbStairs(n): 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) 空间n45 时毫无压力。但面试官通常不会在这里停下他会追问一句空间能不能再省一点因为观察转移方程可以发现计算dp[i]时只用到dp[i-1]和dp[i-2]更早的状态再也不会被使用。那为什么要用一个长度为 n 的数组把它们全部留在内存里3.3 滚动数组从 O(n) 空间降到 O(1)滚动数组的思路就是只保留最近两个状态用两个变量滚动更新def climbStairs(n): if n 2: return n a, b 1, 2 for _ in range(3, n 1): a, b b, a b return b这里要注意一个经典坑如果写成a b b a b那a被覆盖后b拿到的是已经更新过的a结果就错了。Python 的并行赋值a, b b, a b会先计算右边的所有值再统一赋值所以安全。在 C、Java 里必须用一个临时变量或者写成int tmp a b; a b; b tmp;从 O(n) 空间压到 O(1) 空间是这道题最实用的优化。面试时把这层讲清楚比直接默写最优解更能体现你理解动态规划。4. 换个视角看爬楼梯斐波那契和组合数学4.1 和斐波那契数列完全等价列出爬楼梯的结果n11n22n33n45n58这个序列是 1, 2, 3, 5, 8看着眼熟吗它和斐波那契数列 1, 1, 2, 3, 5, 8 错开了一位。斐波那契数列定义 F(1)1F(2)1F(k)F(k-1)F(k-2)。爬楼梯的结果 f(n) F(n1)。这个等价关系有很多用处。比如你可以直接套斐波那契的各种性质也可以用矩阵快速幂优化到大 n 场景。4.2 组合数解法直接数两步的次数这是很多人没注意到的解法把爬楼梯看成组合问题。假设整个爬楼过程中用了 k 次跨 2 阶那么跨 1 阶的次数就是 n - 2k。总步数是总步数 k (n - 2k) n - k这 n-k 步里有 k 步是跨 2 阶的。从 n-k 个位置里选出 k 个位置安排跨 2 阶方法数就是组合数 C(n-k, k)。k 的取值范围是 0 到 ⌊n/2⌋所以答案 Σ C(n-k, k)其中 k 0, 1, ..., ⌊n/2⌋用 Python 可以很简洁地实现import math def climbStairs(n): ans 0 for k in range(n // 2 1): ans math.comb(n - k, k) return ans验证 n4k0C(4,0)1即 1111k1C(3,1)3即 211、121、112k2C(2,2)1即 22总数 5和 DP 结果一致。这个解法时间复杂度 O(n)需要计算组合数实际竞赛中不如 DP 简洁但它提供了一种完全不同的视角对理解相同结果的不同建模方式很有帮助。4.3 通项公式与矩阵快速幂面试加分项既然爬楼梯和斐波那契等价那么斐波那契的所有高级工具都能用。通项公式斐波那契数列的通项公式是F(n) (φ^n - ψ^n) / √5其中 φ (1√5)/2ψ (1-√5)/2。因为 f(n) F(n1)所以爬楼梯的结果也可以直接套公式。不过浮点运算会有精度问题LeetCode 的 n 很小用不上面试提一嘴即可真正能写代码的是矩阵快速幂。矩阵快速幂把递推关系写成矩阵形式[F(n1)] [1 1] [F(n)] [F(n) ] [1 0] [F(n-1)]于是求第 n 项等价于计算矩阵的 n 次方再取第一行第一列。矩阵乘法可以用快速幂模板加速到 O(log n)。def climbStairs(n): def mat_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 mat_pow(M, p): res [[1, 0], [0, 1]] while p: if p 1: res mat_mul(res, M) M mat_mul(M, M) p 1 return res if n 1: return 1 M [[1, 1], [1, 0]] P mat_pow(M, n) return P[0][0]验证一下n1 时返回 1n2 时 M^2 的第一行第一列是 2n3 时是 3符合题意。虽然 n45 用不上这么重的手段但矩阵快速幂是大规模线性递推的标准解法从爬楼梯引出它可以说是性价比最高的学习路径。5. 面试官真正喜欢问的变体从爬楼梯到路径规划5.1 变体一不允许连续爬两级这是我在面试中实际遇到过的变体每次可以爬 1 级或 2 级但不能连续两次都爬 2 级问有多少种方法。如果还用普通 DP会漏掉连续爬 2 级的限制。需要把最后一步的类型也纳入状态one[i]到达第 i 阶且最后一步是跨 1 阶的方法数。two[i]到达第 i 阶且最后一步是跨 2 阶的方法数。转移时注意限制如果最后一步跨 2 阶到达 i那么倒数第二步不能是跨 2 阶到达 i-2。换句话说到达 i-2 的方式必须是最后一步跨 1 阶def climbStairsNoConsecutiveTwo(n): if n 2: return n one [0] * (n 1) two [0] * (n 1) one[1] 1 one[2] 1 # 11 two[2] 1 # 2 for i in range(3, n 1): one[i] one[i - 1] two[i - 1] two[i] one[i - 2] return one[n] two[n]注意two[i] one[i-2]这个式子如果最后一步跨 2 阶从 i-2 到 i那么 i-2 那一步只能是通过跨 1 阶到达的否则就会构成连续两次跨 2 阶。验证 n4普通答案是 5限制后的答案是 4排除了 22 这种方案和代码结果一致。这类变体考察的是状态设计是否够细非常经典。5.2 变体二带代价的爬楼梯LeetCode 746《最小花费爬楼梯》就是这个变体。每阶有体力代价你可以从第 0 阶或第 1 阶开始每次爬 1 或 2 阶目标是到楼顶的总代价最小。状态定义变成最小代价dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])其中dp[i]表示到达第 i 阶的最小花费还没计算从第 i 阶继续向上的费用。def minCostClimbingStairs(cost): n len(cost) dp [0] * (n 1) for i in range(2, n 1): dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]) return dp[n]和爬楼梯的差别只有一个求和变成求 min计数变成最小花费。底层逻辑完全相同。所以在面试中讲爬楼梯时主动带上这个变体会显得你对 DP 的理解不是背题而是真的会迁移。5.3 变体三二维化之后就是路径计数问题爬楼梯是一维两方向的递推从 i-1 来或从 i-2 来。如果把方向扩展到二维就是 LeetCode 62《不同路径》机器人从(0,0)走到(m-1,n-1)每次只能向右或向下问路径数。状态定义变成二维dp[i][j] dp[i-1][j] dp[i][j-1]从上方来或从左方来和爬楼梯从 n-1 来或从 n-2 来是同一个思想。def uniquePaths(m, n): dp [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] dp[i - 1][j] dp[i][j - 1] return dp[m - 1][n - 1]刷题时把 70、746、62、63 串在一起你会发现它们本质上是同一个 DP 模型在不同维度和约束下的表现。这个认知比单独刷十道题都涨经验。6. 我在 Hot100 中的复盘经验这道题该怎么沉淀6.1 算法题不是背代码是背决策链刷到第64题时我已经有个体会算法题不要只背题解要背如果我在面试现场我会按什么顺序讲明白这道题。爬楼梯这道题我的口头讲解链路是先讲递归最后一步只有两种选择所以f(n)f(n-1)f(n-2)指出递归有指数级重复计算提出记忆化记忆化是自顶向下动态规划则是自底向上本质一样用滚动数组把空间压到 O(1)如果要展示知识面还可以补一句它和斐波那契等价可以用矩阵快速幂优化到大 n。这条链路既有复杂度分析又有优化过程比直接写最优解更有说服力。面试官想看到的不是你会不会这道题而是你面对一道题时的思考路径。6.2 同类题目串联表我在复盘时整理过一个串联表方便以后复习题目核心差异关键思路70. 爬楼梯计数型一维递推dp[i]dp[i-1]dp[i-2]746. 最小花费爬楼梯求最小值dp[i]min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])62. 不同路径二维递推dp[i][j]dp[i-1][j]dp[i][j-1]63. 不同路径 II带障碍障碍点 dp091. 解码方法分类讨论强调状态转移的边界条件这个表的作用不是让你背而是让你在做新题时条件反射地识别这题是不是爬楼梯的变形如果是转移方程应该改哪里6.3 我自己踩过的两个坑最后记录两个真实踩过的坑希望你别再掉进去。坑一组合数解法里 k 的范围搞错。我第一次写组合数解法时循环条件写成了for k in range(n1)结果math.comb(n-k, k)在 k 很大时因为n-k k直接抛异常。后来才意识到 k 最多只能是n // 2因为爬 2 阶的次数不可能超过总阶数的一半。这个细节也提醒我数学解法虽然优雅但边界条件比 DP 更容易出错。坑二滚动数组更新顺序搞反。我第一次用两个变量模拟滚动数组时写的是a b b a b结果是错的。因为第一行执行后a已经被覆盖成b了第二行用的不是原来的a。后来我养成一个习惯凡是遇到用两个变量交替更新的场景先用临时变量或 Python 并行赋值不偷懒。还有一个小技巧跑完 AC 后自己把 n45 的结果打印出来看一眼是 1836311903。记住这个数以后写任何滚动数组版本跑完顺手验一下如果输出的不是这个数基本就是更新顺序写错了。这个办法很笨但排查效率极高。爬楼梯这道题看起来简单但把它吃透需要的知识密度其实不低。从递归到动态规划从斐波那契到组合数学从一维递推到二维路径它几乎是动态规划入门的完整教材。如果你也在刷 Hot100别急着跳过它花点时间把每个解法都写一遍值得。