企业官网建设流程全解析

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 种方法（1+1 或者一次爬 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 动态规划：标准递推写法

自底向上的版本就是前面提到的递推公式，直接开一个长度为 n+1 的数组：

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 到 n，dp[i] 表示爬到第 i 阶的方法数。为什么数组长度是 n+1？因为我们要用到下标 n，Python 下标从 0 开始，所以长度为 n+1 才能访问到 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 更新为旧的 curr，curr 更新为两者的和。循环结束后 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)^(n+1) - ((1-√5)/2)^(n+1) ) / √5

直接用这个公式算，对 n 特别大的时候需要用到浮点运算和高精度技巧，处理不好会损失精度。所以LeetCode 场景下我不推荐，但理解这个公式能帮助你串联起算法和数学的联系。以后遇到“求斐波那契数的后几位”这类题目，你就会有额外的手段（矩阵快速幂 + 模运算）可以应对。

这里要提一句，如果面试官问你“有没有 O(log n) 的方案”，矩阵快速幂是最稳妥的回答，通项公式虽然理论上也行，但实现起来容易在精度上翻车，不是每个人都驾驭得了。

3.3 三种方案怎么选

直接给个结论，方便你按场景决策：

刷题阶段，我认为最值得掌握的方案是滚动数组，代码量少、思路清晰、还能顺手展示你对空间复杂度的敏感性。很多人以为面试题写出 O(n) 空间就够了，实际上“能不能优化”往往是区分普通候选人和优秀候选人的分水岭。

4. 题目变形与工程场景联想

学会一道题不算本事，能把它迁移到别的场景才算真正掌握。爬楼梯类型的问题在现实里其实有大量变体，面试官也格外喜欢在变体上做文章。

4.1 常见的变形题

变形一：每次可以爬 1 或 2 或 3 个台阶。递推式变成 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，初始条件需要好好推。dp[1] = 1，dp[2] = 2，dp[3] = 4（1+1+1、1+2、2+1、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(n+1)，因为爬楼梯序列是 1, 2, 3, 5, 8...，而斐波那契是 1, 1, 2, 3, 5, 8...。如果你直接用斐波那契的公式，搞错一位就是错答案。写之前先在纸上列几个小值对照一下，至少我吃过这个亏，印象特别深。

第三个坑：状态定义不清晰。有些解法把 dp[i] 定义成“恰好还有 i 阶要爬”的方案数，从尾部往前推；有的把 dp[i] 定义成“从第 0 阶爬到第 i 阶”的方案数。两种都能写对，但混在一起容易头晕。我的建议是统一用“从起点爬到第 i 阶”的语义，从头往后推，思路最自然，也不容易出错。

5.2 如何举一反三地练 DP

爬楼梯这道题吃透之后，我建议你用同样的方法尝试以下节奏：

1. 每天做一道“一维 DP”题，持续一周，重点练习从暴力递归到滚动数组的优化链路。
2. 每周挑一天，把本周做过的题重新用“记忆化搜索 + 迭代 DP + 滚动数组”三种方案各写一遍，加深对状态转移的肌肉记忆。
3. 试着给做过的每一道 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 的时候省了太多力气。这道仅有几行代码的简单题，真的是刷题路上最值得反复咀嚼的一块基石。