企业官网建设流程全解析

先说个真实感受：爬楼梯这道题，在很多面试场景里已经快被问出包浆了。我见过不少人能把答案背得滚瓜烂熟，f(n) = f(n-1) + f(n-2)顺手就敲出来，但你让他解释一下为什么是这个公式、递归和动态规划到底差在哪、为什么裸递归一跑就卡，他往往支支吾吾讲不清楚。这其实很能说明一个问题：动态规划的核心从来不是背转移方程，而是搞懂状态从哪里来、到哪里去、每一步为什么这么选。这篇东西我想用Python把爬楼梯彻底拆开，从暴力递归讲到记忆化搜索，再到标准的自底向上DP、滚动数组空间压缩，最后聊一聊它在面试里常见的变形考法。适合刚接触DP的人从头跟到尾，也适合刷过题但讲不清原理的朋友重新补补课。

1. 从“最后一步”看题面：为什么答案长成斐波那契的样子

1.1 先把n=1到n=4手算一遍

题目本身非常简单：假设你正在爬一段楼梯，一共n级，每次可以选择爬1级或者2级台阶，问有多少种不同的方法可以爬到楼顶。

先别急着套公式，咱们动手枚举一下，找找感觉：

• n=1：只有[1]这一种走法，答案是1。
• n=2：可以是[1, 1]，也可以是[2]，答案是2。
• n=3：[1, 1, 1]、[1, 2]、[2, 1]，答案是3。
• n=4：[1, 1, 1, 1]、[1, 1, 2]、[1, 2, 1]、[2, 1, 1]、[2, 2]，答案是5。

1、2、3、5，这不就是斐波那契数列往里挪了一位吗？很多人到这里就得出结论了：答案就是斐波那契。这种观察没错，但如果你只是记住“斐波那契”，遇到题目稍微变个花样——比如每级台阶带个花费、或者限制你不能连续爬两级——你就又不会了。所以真正要搞明白的是：这个数字规律背后的结构是什么。

1.2 最后一步的拆解：互斥且完备的两种到达方式

想爬到第n级台阶，你的最后一步只有两种可能：要么从第n-1级跨1级上来，要么从第n-2级跨2级上来。不存在第三种情况。

于是方案总数就变成了：

f(n) = f(n-1) + f(n-2)

这个式子看起来简单，但背后是两个很重要的判断：

• 互斥：最后一步跨1级和跨2级，是两种完全不同的方案，不会重叠。
• 完备：所有合法方案，最后一步必然属于这两种之一，没有漏掉的。

这就是动态规划里很典型的“从后往前想”的思路。很多人一上来就想着从头开始模拟怎么走，比如第一步迈1级还是2级，然后开始枚举路径。那样也能做，但状态一下子就多了。倒过来从终点看，反而只有两个分支，干净利落。

1.3 “无后效性”和“重叠子问题”：动态规划的两把钥匙

为什么爬楼梯能作为动态规划入门第一题？因为它身上同时具备了DP两个最核心的特征：

第一个叫无后效性。意思是，f(n)的取值只关心“当前站在第几级台阶”，完全不关心你是怎么走到这一级的。你是从第0级一路小跑上来的，还是中间歇了三次，对后续的方案数没有任何影响。这个性质非常重要，它保证了我们可以放心地用子问题的答案去拼父问题。

第二个叫重叠子问题。计算f(n)需要f(n-1)和f(n-2)，计算f(n-1)又需要f(n-2)和f(n-3)。你会发现f(n-2)在计算过程中被反复用到。这种“同一个子问题被多次求解”的情况，就是重叠子问题。动态规划两大优化方向——自顶向下记忆化和自底向上填表——本质上都是在处理它。

所以这道题虽然简单，但它把DP的骨架完整展示了一遍：定义状态、分析转移、找到边界、处理重叠。

2. 裸递归的复杂度灾难：为什么n=40就能卡到怀疑人生

2.1 最直观的递归代码

先把最直觉的写法亮出来，很多人的第一反应就是这个：

def climb_stairs_recursive(n: int) -> int: if n <= 2: return n return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

这段代码逻辑上完全正确。n=1返回1，n=2返回2，n=3开始进入递归，调两次自身再求和。你用它跑n=10，秒出；跑n=30，稍微顿一下；跑到n=40，肉眼可见地开始卡；n=50，基本可以起身倒杯水。

为什么？因为它的时间复杂度是O(2^n)，指数级增长。

2.2 递归树一眼看穿重复计算

我们以n=5为例，画出调用关系：

climb(5) ├── climb(4) │ ├── climb(3) │ │ ├── climb(2) │ │ └── climb(1) │ └── climb(2) └── climb(3) ├── climb(2) └── climb(1)

很直观地能看到，climb(3)被算了两次，climb(2)被算了更多次。n越大，这种重复越严重。整个结构是一棵近乎满二叉树的递归树，树的节点总数就是函数被调用的总次数。

每次调用都要做一次加法运算，哪怕单次成本很低，架不住数量是天文数字。

2.3 用调用次数说话

具体数字比任何感觉都更有说服力。我们把递归调用次数统计一下，爬楼梯这个递归树的节点个数有现成结论：

调用次数 = 2 * F(n+1) - 1

其中F是斐波那契数列。我直接列几个典型值：

Python本身是解释型语言，函数调用开销比编译型语言大得多。我在本机实测，n=40的裸递归大概要卡几十秒，n=50直接在那边傻算。你要是真在面试现场写出这段代码，面试官下一个问题必然是：“你这个复杂度是多少？还能优化吗？”很多背答案的人就是倒在这一步——代码写得出来，复杂度说不出，或者随口答了个O(n)，因为只看到了一层调用。

正确的分析方法是画递归树：每个节点代表一次计算，树的规模是指数级的，所以时间复杂度一定是O(2^n)。搞懂这一点，你才算真的看懂了这题的难点。

3. 记忆化搜索：给递归加一层缓存，复杂度立刻线性

3.1 手写字典缓存与lru_cache

既然问题是重复计算，那最直接的思路就是：算过的结果存下来，下次直接查表。

最简单的做法，在递归函数外面套一个字典：

def climb_stairs_memo(n: int) -> int: cache = {} def dfs(k: int) -> int: if k <= 2: return k if k in cache: return cache[k] cache[k] = dfs(k - 1) + dfs(k - 2) return cache[k] return dfs(n)

也能用Python标准库自带的最长缓存装饰器，代码更短：

from functools import lru_cache @lru_cache(maxsize=None) def climb_stairs_lru(n: int) -> int: if n <= 2: return n return climb_stairs_lru(n - 1) + climb_stairs_lru(n - 2)

这两种写法本质是一样的，都是把“当前输入对应的答案”记录下来，避免同样的n被反复算。这就是记忆化搜索，也叫自顶向下动态规划。

3.2 为什么加了缓存就变成O(n)

关键点在这里：加了缓存之后，每个n只会被真正计算一次。

从k=n开始，一路递归到k=1和k=2，回到k=3的时候算出结果并缓存，再回到k=4时直接用，然后k=5也直接用……本质上每个节点只访问一次，所以递归树的节点数从2^n降到了O(n)。配合递归调用栈的开销，时间复杂度是O(n)，空间复杂度也是O(n)（缓存字典加上递归栈深度）。

这一步优化有多明显？我拿相同环境对比过：n=40，裸递归几十秒，加了记忆化直接是个位数毫秒。这就是“重叠子问题”被消化的直接体现。

3.3 记忆化的隐藏坑：Python递归深度限制

记忆化搜索很优雅，但有一个很现实的限制——Python的递归深度默认只有大概1000层。

也就是说，当你n=10000的时候，哪怕有缓存，递归到1000层左右就会抛出RecursionError: maximum recursion depth exceeded。爬楼梯这个递推深度正好差不多等于n，所以大输入下记忆化方案会直接崩。

解决办法有两个：一是sys.setrecursionlimit()调大递归上限，但调太大有栈溢出的风险，治标不治本；二是干脆放弃递归，改用自底向上的循环迭代。对于这种递推关系明确的题目，我推荐后一种。

4. 标准的自底向上DP：状态定义的锚点作用

4.1 一张dp数组解决所有问题

自底向上的思路是从已知推未知。既然边界是f(1)=1、f(2)=2，那f(3)由它们相加得到，f(4)由f(3)和f(2)得到，一路推到f(n)。

用数组实现非常直观：

def climb_stairs_dp(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)（因为开了长度为n+1的数组）。

4.2 从状态定义到转移方程，正确顺序是什么

很多新人写DP最大的困惑是：状态转移方程到底怎么“变”出来？我建议按照固定顺序来走：

1. 先定义状态：dp[i]表示爬到第i级台阶的方法总数。
2. 再找转移：最后一步只能从i-1或i-2来，所以dp[i] = dp[i-1] + dp[i-2]。
3. 再定边界：dp[1]=1，dp[2]=2。
4. 最后想遍历顺序：从小往大算，保证dp[i-1]和dp[i-2]已经算好。

状态定义是整个DP题的“锚点”。定义不同，转移方程就不同。比如我们后面要讲的最小花费爬楼梯，状态定义从“方案数”改成“最小成本”，转移方程立刻变成min而不是加号。如果你一上来就盯着转移方程看，那就本末倒置了。

4.3 边界条件的踩坑细节

这个写法里有几个容易出错的细节，我一一提一下：

• n=0怎么办？爬0级台阶严格来说应该是0种方法，但也有定义成1种（空方案）的版本。刷题时看清题目要求，通常n是正整数，直接if n <= 2: return n就安全了。
• dp数组长度用n+1而不是n，因为下标要能取到dp[n]。
• 循环从3开始，别从1开始，否则会用尚未初始化的dp[0]。
• 如果你习惯斐波那契的解法，把状态定义成dp[0]=1, dp[1]=1也行，得到的结果完全一样，只是边界稍微不同。

这种数组写法最大的优点是：所有中间结果都在表里，将来想改造成“带权重的爬楼梯”或者需要回溯方案时，数组能提供完整的历史信息。

5. 滚动数组空间压缩：从O(n)到O(1)的最后一公里

5.1 观察依赖关系，扔掉所有历史记录

看这个递推式：

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

你发现没有，算dp[i]的时候，只需要前面两个值。dp[0]到dp[i-3]全都不会再被用到了。可是我们刚才的数组写法却把它们全部保存了下来，这就有空间浪费。

在很多在线评测系统里，爬楼梯这道题的内存要求很宽松，你开数组完全不会出问题。但面试官通常会追加一句：“你能不能把空间复杂度优化到O(1)？”这时候滚动数组就该登场了。

5.2 两个变量滚着走

既然只依赖前两个值，那就只保留前两个值：

def climb_stairs_optimized(n: int) -> int: if n <= 2: return n a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b

这个写法非常经典。a相当于dp[i-2]，b相当于dp[i-1]。每循环一轮，(a, b)整体向右滚动一位，最后b就是dp[n]。

时间复杂度还是O(n)，空间复杂度降到了O(1)。对于n特别大的情况，比如n=10的9次方级别，数组方案直接内存爆炸，但滚动数组依然能跑，只不过Python里跑这么多次循环本身也需要时间，所以实际面试不会出那么极端的输入。

5.3 进阶：矩阵快速幂能把复杂度压到O(log n)

这里提一个进阶方向，但不建议新手一上来就学。爬楼梯的递推本质上可以写成矩阵形式：

[ f(n) ] [1 1] [ f(n-1) ] [ f(n-1) ] = [1 0] [ f(n-2) ]

矩阵的n次方可以用快速幂在O(log n)时间算出来，几何级数级别的加速。但说实话，面试中能让候选人写出滚动数组已经算合格了，问矩阵快速幂的极少——一般那是在考数学而不是考DP。我自己的建议是：先把滚动数组练熟，矩阵快速幂作为知识储备了解一下即可。

6. 面试与实战中的花样变形：爬楼梯的一族亲戚

6.1 最小花费爬楼梯：从计数变成求最值

这可能是爬楼梯最经典的变形题。题目大致是这样的：每个台阶都有一个体力花费cost[i]，站在第i级台阶要支付cost[i]的费用，你可以从第0级或第1级出发，每次可以跨1级或2级，问到达楼顶的最小总花费是多少。

状态定义需要变一下：dp[i]表示到达第i级台阶并支付完这里的费用后的最小总花费。转移方程变成：

dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

意思很直接：要到第i级，你只能从i-1或i-2跨过来，选一个花费更小的方案，再付第i级自己的费用。

代码用滚动数组优化后是这样的：

def min_cost_climb_stairs(cost: list[int]) -> int: n = len(cost) if n == 2: return min(cost[0], cost[1]) a, b = cost[0], cost[1] for i in range(2, n): a, b = b, min(a, b) + cost[i] return min(a, b)

这个版本有两个容易出错的点。第一是答案不能用dp[n]直接收尾，因为最后一步可能从n-2直接跨到楼顶而不用支付dp[n-1]的费用，所以答案要取dp[n-1]和dp[n-2]里的较小值。第二是cost数组长度小于2的边界情况，需要单独处理。

你看，同样的题骨架，状态定义从“方案数”换成“最小代价”，transfer就从加法变成了min加法。这就是定义状态先行带来的好处。

6.2 步长扩展和“不能连续跳2级”的二维状态

再聊聊其他变形。

如果每次可以爬1、2、3级，转移方程立刻变成：

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

本质上没有任何新东西，只是转移的宽度增加了。如果再扩展成“一次可以爬1到k级”，就变成了一段连续区间求和，可以用前缀和进一步优化到O(n)。

还有一种更刁钻的变形：规定不能连续两次都跨2级台阶。这时候原来的一维状态就不够用了，因为你得知道前一步是不是跨了2级，才能判断这一步能不能再跨2级。于是状态要扩成二维：

dp[i][0] = 最后一步跨1级，到达第i级的方法数 dp[i][1] = 最后一步跨2级，到达第i级的方法数

转移方程变成：

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

这样就自然引入了“二维DP”的概念。爬楼梯这道题的神奇之处就是能一步步引导你从一维递推到二维状态，非常适合用来理解状态设计的维度为什么需要扩展。

6.3 面试官从这道题能看到什么：递进追问的四个层次

我参加过不少技术面试，自己也面过候选人，总结了一下，面试官在爬楼梯这道题上通常有四个递进层次：

• 第一层：能写出递归版本，复杂度分析正确。考察基础编码能力和递归理解。
• 第二层：能指出递归的重复计算问题，并给出记忆化或DP方案。考察问题分析能力。
• 第三层：能写出滚动数组O(1)空间版本，并解释为什么安全。考察代码品味和空间意识。
• 第四层（加分项）：面对变种能快速调整状态定义，比如最小花费版本、二维状态版本。考察知识迁移能力。

所以我的建议很明确：练习时别只背最优解代码，而是老老实实从递归开始，把每一步优化的动机和代价都搞清楚。这道题虽然小，但它把“暴力 → 记忆化 → 自底向上DP → 滚动数组”这一整条优化路径完整走了一遍。你能顺着这条路径讲清楚，动态规划基础基本就过关了。

最后分享一个我自己的做题习惯：拿到任何DP变体，不要在脑子里空想，先把dp[i]的定义写在草稿纸最上面，然后问自己三个问题——这个状态由哪些更小的状态转移而来？边界条件是什么？遍历顺序怎么保证子状态先算好？三句话写清楚再动手写代码，正确率会高很多。爬楼梯这道题我刷过很多遍，每次重新做一遍都还能发现一点新的理解角度，这大概就是基础题的魅力所在。