企业官网建设流程全解析

LeetCode Hot100 刷到第64题，遇到了一道几乎所有人都说自己会做的题：70. 爬楼梯。题目本身短到只有两句话，示例数据也小到不用动脑子——n=3，答案是3。但我还是把它单独拎出来写，原因是，这道题在 Hot100 里的位置太有代表性了：它横跨递归、动态规划、组合数学和矩阵快速幂四个层次，是把"入门题"吃成"进阶题"的最佳样本。

如果你也在刷 Hot100，可能和我一样，前面几十道题已经见了各种二叉树、链表、滑动窗口，突然来一道这么简单的爬楼梯，反而会犹豫：这题真的需要总结吗？我的体会是，真正需要记录的不是题目本身，而是这道题背后的一整条优化链路。从暴力递归到记忆化，从动态规划到滚动数组，再到矩阵快速幂，每一步都能讲出不少细节。这篇文章就按我复盘时的思路完整拆一遍。

1. 爬楼梯这道题，为什么值得被放进 Hot100

1.1 题目在说什么

题目背景很生活化：你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶。

示例也直观：

• n = 2，答案是 2：1 阶 + 1 阶，或者直接跨 2 阶。
• n = 3，答案是 3：1+1+1、1+2、2+1。

我第一次读题时的反应是：这不就是斐波那契吗？确实，从结果上看它和斐波那契数列高度重合，但如果你只满足于"斐波那契"四个字，就会错过这道题真正的教学价值。

LeetCode 上这道题的约束是1 <= n <= 45，数值很小，哪怕用 O(2^n) 的暴力递归，n=45 也已经会卡到怀疑人生；但用动态规划只需要 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 阶的方法数。

代码只有三行，逻辑也正确。但如果你直接拿它去跑 LeetCode，n 稍微大一点就会超时。因为这里面有大量重复计算。

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)。虽然 n=45 不是天文数字，但指数级增长下，重复计算的次数会膨胀到完全无法承受。这也是为什么递归写法虽然"正确"，却不实用的根本原因。

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)。递归深度也不会超过 45，Python 默认递归深度足够。

从"暴力递归"到"记忆化搜索"，这一步能很自然地引出动态规划：既然所有子问题都已经只计算一次，那我为什么不能直接从小到大算一遍呢？这就进入正解了。

3. 动态规划的正解：状态转移与滚动数组

3.1 状态定义从"递归返回"反推

我在面试中比较喜欢的讲法是：不要凭空背状态定义，而是从递归函数的返回值去反推。

递归函数dfs(i)返回的是"爬到第 i 阶的方法数"，所以动态规划的状态也很自然：

dp[i]表示爬到第 i 阶的方法数。

转移方程就是递归体的镜像：

dp[i] = dp[i-1] + dp[i-2]

初始条件有两种写法。主流写法是：

• dp[1] = 1
• dp[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) 空间，n=45 时毫无压力。

但面试官通常不会在这里停下，他会追问一句：空间能不能再省一点？因为观察转移方程可以发现，计算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 和斐波那契数列完全等价

列出爬楼梯的结果：

• n=1：1
• n=2：2
• n=3：3
• n=4：5
• n=5：8

这个序列是 1, 2, 3, 5, 8，看着眼熟吗？它和斐波那契数列 1, 1, 2, 3, 5, 8 错开了一位。

斐波那契数列定义 F(1)=1，F(2)=1，F(k)=F(k-1)+F(k-2)。爬楼梯的结果 f(n) = F(n+1)。

这个等价关系有很多用处。比如你可以直接套斐波那契的各种性质，也可以用矩阵快速幂优化到大 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

验证 n=4：

• k=0：C(4,0)=1，即 1+1+1+1
• k=1：C(3,1)=3，即 2+1+1、1+2+1、1+1+2
• k=2：C(2,2)=1，即 2+2

总数 5，和 DP 结果一致。

这个解法时间复杂度 O(n)，需要计算组合数，实际竞赛中不如 DP 简洁，但它提供了一种完全不同的视角，对理解"相同结果的不同建模方式"很有帮助。

4.3 通项公式与矩阵快速幂（面试加分项）

既然爬楼梯和斐波那契等价，那么斐波那契的所有高级工具都能用。

通项公式：

斐波那契数列的通项公式是：

F(n) = (φ^n - ψ^n) / √5

其中 φ = (1+√5)/2，ψ = (1-√5)/2。

因为 f(n) = F(n+1)，所以爬楼梯的结果也可以直接套公式。不过浮点运算会有精度问题，LeetCode 的 n 很小用不上，面试提一嘴即可，真正能写代码的是矩阵快速幂。

矩阵快速幂：

把递推关系写成矩阵形式：

[F(n+1)] [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]

验证一下：n=1 时返回 1，n=2 时 M^2 的第一行第一列是 2，n=3 时是 3，符合题意。

虽然 n=45 用不上这么重的手段，但矩阵快速幂是大规模线性递推的标准解法，从爬楼梯引出它，可以说是性价比最高的学习路径。

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 # 1+1 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 阶。

验证 n=4，普通答案是 5，限制后的答案是 4（排除了 2+2 这种方案），和代码结果一致。这类变体考察的是"状态设计是否够细"，非常经典。

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题时我已经有个体会：算法题不要只背题解，要背"如果我在面试现场，我会按什么顺序讲明白这道题"。

爬楼梯这道题，我的口头讲解链路是：

1. 先讲递归：最后一步只有两种选择，所以f(n)=f(n-1)+f(n-2)；
2. 指出递归有指数级重复计算，提出记忆化；
3. 记忆化是自顶向下，动态规划则是自底向上，本质一样；
4. 用滚动数组把空间压到 O(1)；
5. 如果要展示知识面，还可以补一句"它和斐波那契等价，可以用矩阵快速幂优化到大 n"。

这条链路既有复杂度分析，又有优化过程，比直接写最优解更有说服力。面试官想看到的不是你会不会这道题，而是你面对一道题时的思考路径。

6.2 同类题目串联表

我在复盘时整理过一个串联表，方便以后复习：

这个表的作用不是让你背，而是让你在做新题时条件反射地识别：这题是不是爬楼梯的变形？如果是，转移方程应该改哪里？

6.3 我自己踩过的两个坑

最后记录两个真实踩过的坑，希望你别再掉进去。

坑一：组合数解法里 k 的范围搞错。我第一次写组合数解法时，循环条件写成了for k in range(n+1)，结果math.comb(n-k, k)在 k 很大时因为n-k < k直接抛异常。后来才意识到 k 最多只能是n // 2，因为爬 2 阶的次数不可能超过总阶数的一半。这个细节也提醒我：数学解法虽然优雅，但边界条件比 DP 更容易出错。

坑二：滚动数组更新顺序搞反。我第一次用两个变量模拟滚动数组时，写的是：

a = b b = a + b

结果是错的。因为第一行执行后，a已经被覆盖成b了，第二行用的不是原来的a。后来我养成一个习惯：凡是遇到"用两个变量交替更新"的场景，先用临时变量或 Python 并行赋值，不偷懒。

还有一个小技巧：跑完 AC 后，自己把 n=45 的结果打印出来看一眼，是 1836311903。记住这个数，以后写任何滚动数组版本，跑完顺手验一下，如果输出的不是这个数，基本就是更新顺序写错了。这个办法很笨，但排查效率极高。

爬楼梯这道题，看起来简单，但把它吃透需要的知识密度其实不低。从递归到动态规划，从斐波那契到组合数学，从一维递推到二维路径，它几乎是动态规划入门的完整教材。如果你也在刷 Hot100，别急着跳过它，花点时间把每个解法都写一遍，值得。