企业官网建设流程全解析

刷到 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 很小的时候跑得飞快，看上去完全没问题。我在本地测试的时候，n=10秒出，n=30能感觉到等待，n=45直接风扇狂转——等了几十秒还没返回结果。问题就出在这里。

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 个小时。实际情况当然没这么夸张，因为中间会有重复子树的合并效应，但 n=45 时跑几十秒是实实在在的。

提示：暴力递归的时间复杂度是 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) 空间。n=45 在这种写法下瞬间返回。

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 只有 45，O(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(n+1), 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^(n+1) - psi^(n+1)) / sqrt(5) phi = (1 + sqrt(5)) / 2 psi = (1 - sqrt(5)) / 2

理论上这个公式能 O(1) 求结果，但实际工程里，sqrt(5)是浮点数，n 稍大一点就会因为浮点误差导致结果不精确。就算用round修正，也有风险。我自己只在两种情况下用通项公式：一是在论文里为了展示数学推导，二是在高频交易或量化场景中需要近似值。刷题或面试时，用通项公式反而是最不推荐的答案，因为它掩盖了你对递推本质的掌握程度。

提示：如果题目要求结果对 1e9+7 取模，矩阵快速幂是标准做法，通项公式中的浮点运算没法直接处理取模。

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，这是出题人刻意为之的边界。但如果你把同样的代码提交到别的 OJ，n 改成 46，C++ 的 int 就直接溢出了，返回一个负数，你会调试到怀疑人生。

所以我的建议是：不管题目给没给范围，只要是递推求数值的题，默认用 long long（C++）、long（Java）或者 Python 的大整数。反正 Python 没有溢出问题，但 Java 和 C++ 必须警醒。

7.2 递归深度的边界问题

记忆化搜索虽然写着方便，但递归深度是硬约束。如果你用 Python，默认递归限制是 1000 层（可以通过 sys.setrecursionlimit 调大，但默认别依赖）。所以在 n 比较大的题目上，别用递归写法去赌。面试时选择自底向上的循环，不仅能避开这个坑，还显得你更老练。

7.3 提交前跑一遍边界测试

我在刷题插件里给自己定了一条铁律：写完代码先跑 n=1、n=2、n=3 三个用例，再跑一个中等值和一个大值。虽然很简单，但能过滤掉 80% 的边界错误。比如很多人把 dp 数组开成n而不是n+1，然后访问dp[n]时报数组越界；还有人把if n <= 2: return 2这种逻辑漏掉，导致 n=1 返回 2。

拿这道题实测，我建议至少验证三组：

• n=1，人工答案 1
• n=2，人工答案 2
• n=3，人工答案 3
• n=45，应该输出 1836311903

最后一个数字我全靠经验记忆：1836311903。写错一个数立刻能发现。

7.4 从刷题到工程思维的迁移

最后说点实在的。有人问，爬楼梯这种题除了面试到底有什么用？我后来在业务里接触过爬虫的调度路径计数、前端的路由层级方案枚举、甚至 CI 流程里步骤组合的可行性判断，底层思路都有影子。真实项目不会把题目原封不动搬过来，但“把大问题拆成最后一步加前面子问题”的思维模型，是能复用一辈子的。

我自己在第二遍刷 Hot 100 的时候，把每道简单题都强迫自己多想一步。比如这题，我会额外问自己：如果允许相邻两步不能都爬 2 阶，怎么改？如果每步能爬的阶数是一个数组[1,2,4]，状态转移又怎么写？这些延伸训练能让你在面试中遇到任何变体都不慌，因为你已经把底层逻辑吃透了。爬楼梯这道题就像算法领域的“举重入门”，练好了，后面的硬拉和挺举才有基础。