企业官网建设流程全解析

刷题计划推到第37天，遇到了一道绕不开的经典动态规划题：746. 使用最小花费爬楼梯。题目本身不长，场景也特别生活化：数组cost里存着每一级台阶的过路费，你可以选择从第0级或第1级起步，每次向上走1级或2级，问爬到顶层最少要掏多少钱。对刚开始接触动态规划的人来说，这道题几乎是完美的入门样本——它把状态定义、递推公式、初始化、遍历顺序这四个DP核心部件全部串了一遍，而且坑不多不少，刚好够你长记性。这篇文章就记录我从读题到写出滚动数组优化的完整过程，也会把那些看答案以为会了、一动手就崩的细节单独拎出来讲清楚。

1. 先别急着写代码：把“顶部在哪”这个小坑填平

1.1 题面翻译成数学模型

把题目翻译成严谨一点的说法：有一个长度为n的数组cost，cost[i]表示“当你踩到第i个台阶时需要支付的费用”。你可以从下标0或者下标1的台阶开始，之后每一次移动可以选择向上走1级或者2级。目标是从起点走到“楼梯顶部”，要求总花费最小。

这里最先要确认的，是对“顶部”的理解。顶部并不是数组的最后一个下标n-1，而是数组末尾再往上那一格——你可以理解为爬完所有台阶之后站到的那片平地。下标0到n-1一共是n级台阶，最后一步有两种可能：从下标n-1的位置走一级到达顶部，或者从下标n-2的位置直接跨两级、越过下标n-1到达顶部。

这个点太容易被忽略了。很多人把“爬完数组里的最后一级台阶”当成“到顶”，最后返回dp[n-1]，结果在示例上就直接翻车。把这个位置关系先钉死在脑子里，后面所有写法都不容易跑偏。

1.2 用示例验证“顶部在数组外”

拿示例cost=[10,15,20]来验证。按照题意：

• 从下标1起步，交15，然后跨两步越过下标2直接到顶，总花费15；
• 从下标0起步，交10，走到下标1再交15，总计25，再跨一步到顶；
• 从下标0起步，交10，然后直接跨两步越过下标1和2到顶，总花费10。

所以正确答案是min(10,15)=10，而很多人会算出15或者20，就是因为在“要不要踩最后一阶”这件事上产生了分歧。特别是“从下标0起步，跨两步到顶”这条路线，整个过程压根没有踩到下标2，如果代码里把答案设成dp[n-1]，等于强制要求最后一阶必须被踩，那自然就错了。

1.3 贪心为什么不行

有人可能会想：每次都挑花费最小的台阶走，不就行了？这个思路听起来合理，但经不起反例。看cost=[1,2,10,2,1,1]这个用例。

贪心的做法是：起步选便宜的第0级，交1；站在第0级比较第1级和第2级，2比10便宜，于是走到第1级，再交2；站在第1级比较第2级和第3级，2比10便宜，于是跨到第3级，再交2；站在第3级比较第4级和第5级，两边都是1，不管选哪边，之后还得再交1才能到顶。贪心路线总花费1+2+2+1=6。

但最优解只需要5：从第1级起步交2，跨两步到第3级交2，再走到第4级交1，最后跨一步越过第5级到顶，总共2+2+1=5。问题出在起步那一下——贪心贪图第0级便宜1块钱，后面反而被逼着多踩了一个台阶。这就是典型的“局部最优不保证全局最优”。当前一步的选择会影响后面能踩到哪些台阶，这种前两步决策互相牵制的问题结构，正是动态规划的信号。

2. 状态定义的分岔口：dp[i]到底代表什么

2.1 定义A：到达第i级并已经付过费

我习惯先把状态定义写清楚：dp[i]表示“到达下标i的台阶，并且已经支付了cost[i]之后，累计的最小花费”。也就是说，dp[i]里已经包含踩上这一阶要交的钱。

在这个定义下，递推公式非常顺。要到达下标i，最后一步只能来自i-1跨一级或i-2跨两级，到达之后再补交cost[i]，所以：

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

初始化也明确：dp[0]=cost[0]，dp[1]=cost[1]。题目说可以从0或1起步，起步不是免费的，选哪一级起步就必须付哪一级的钱。

这个定义下答案怎么取？因为顶部在数组外面，最后一步不需要再交钱。你可以从下标n-1跨一级到顶，也可以从下标n-2跨两级越过n-1到顶，所以答案是：

min(dp[n-1], dp[n-2])

2.2 定义B：dp[i]表示爬到第i层位置的花费

另一种常见写法是让dp数组长度变成n+1，下标i表示“楼层位置”，而不是“台阶下标”。位置0是起点地面，位置1是第一级台阶，位置n是顶部。注意这里i和cost的下标错开了一位：要爬到位置i（i≥2），最后一步从i-1或i-2过来，踩到的台阶下标是i-1，需要交cost[i-1]。

于是递推公式写成：

dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]，i从2到n

初始化是dp[0]=0（还没上台阶，不花钱），dp[1]=cost[0]（站在第一级台阶，交第一级的钱）。返回值直接取dp[n]，因为n这个位置就是顶部。

这两种定义都能AC，但绝对不能混着写。我最常看到的问题就是：代码里用了n+1长度的dp，递推时却写cost[i]，结果i=n时直接数组越界，或者答案差一个身位。根源就是没有锁定“i到底是台阶下标还是楼层位置”。

2.3 两种定义怎么选

给新手的建议是选定义B，理由是返回dp[n]非常直观，不用在最后一步到底是n-1还是n-2上纠结。但定义B的索引错位比较抽象，写的时候要时刻记得cost[i-1]这个偏移。

老手反而更喜欢定义A，因为索引和cost完全对齐，递推式是纯粹的min(dp[i-1],dp[i-2])+cost[i]，逻辑最干净。我自己最终常写的是定义A，但无论用哪种，开头一定先写一行注释：

// dp[i]: 到达台阶i并支付cost[i]后的最小花费，答案 = min(dp[n-1], dp[n-2])

别小看这一行字。动态规划题里，状态定义一旦含糊，后面所有代码都会跟着含糊。先写注释再写代码，是我在DP题上最值回票价的一个习惯。

3. 动笔实践：两套写法加一套滚动数组

3.1 写法一：dp长度等于n，返回倒数两位的较小值

用定义A直接实现，C++代码大概是这样的：

int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> dp(n); dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < n; i++) { dp[i] = min(dp[i-1], dp[i-2]) + cost[i]; } return min(dp[n-1], dp[n-2]); }

这个版本有两个容易翻车的点。第一，题目数据范围一般保证n≥2，如果n=1，dp[1]会越界，所以面试手写时最好加个if (n == 1) return cost[0];的兜底。第二，返回值必须是min(dp[n-1], dp[n-2])，少看一眼就会写成dp[n-1]，这在[10,15,20]这个用例上会直接得到30而不是10。

3.2 写法二：dp长度等于n+1，把顶部做成状态

用定义B写出来是另一种味道：

int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> dp(n + 1); dp[0] = 0; dp[1] = cost[0]; for (int i = 2; i <= n; i++) { dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]; } return dp[n]; }

这个版本的核心是理解cost[i-1]这个偏移。位置i是个“楼层数”，它对应的台阶下标是i-1。我在练习时见过有人把cost[i-1]写成cost[i]，结果当i=n时越界；还有人把dp[1]初始化成0，等于白送第一级台阶，答案就比正确答案少了cost[0]。这些错误都不是逻辑不会，而是定义没写清楚。

3.3 滚动数组：从O(n)到O(1)

看递推公式就会发现，dp[i]只依赖dp[i-1]和dp[i-2]，前面的状态用完之后就再也用不到了。所以完全可以用两个变量滚动前进，把空间复杂度从O(n)压到O(1)：

int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); int prev2 = cost[0]; // 相当于 dp[0] int prev1 = cost[1]; // 相当于 dp[1] for (int i = 2; i < n; i++) { int cur = min(prev1, prev2) + cost[i]; prev2 = prev1; prev1 = cur; } return min(prev1, prev2); }

滚动数组的bug高发点是更新顺序。必须先执行prev2 = prev1，再执行prev1 = cur。如果顺序写反，prev2会被cur覆盖掉，下一轮迭代就丢失了dp[i-2]的值，整个计算直接崩掉。我每次写滚动数组前都会先问自己一句：“下一轮需要哪两个值？”想清楚再动手。

3.4 Python版本与语言差异

Python版本我通常也写成滚动形式，利用元组同时赋值可以少踩一个坑：

from typing import List def minCostClimbingStairs(cost: List[int]) -> int: n = len(cost) prev2, prev1 = cost[0], cost[1] for i in range(2, n): cur = min(prev1, prev2) + cost[i] prev2, prev1 = prev1, cur return min(prev1, prev2)

Python里prev2, prev1 = prev1, cur是同时赋值的，不存在C++里那种覆盖顺序问题。调试时我习惯在循环里临时加一句print(cur)，把每次算出来的“dp值”打出来看，配合下面的手推用例，能很快定位到是初始化错了还是递推公式错了。

4. 手推用例：让递推公式从纸面落到地面

4.1 用[10,15,20]完整推一遍

用定义A手推一遍这个小例子，感受一下状态是怎么流动的。cost=[10,15,20]：

• dp[0] = 10；
• dp[1] = 15；
• i=2：dp[2] = min(dp[0], dp[1]) + cost[2] = min(10,15) + 20 = 30；
• 答案 = min(dp[1], dp[2]) = min(15, 30) = 10。

注意，最优路线是从下标0起步，交10，直接跨两步越过下标1和2到顶。所以dp[2]=30这个“到达最后一阶”的状态，在答案计算中根本用不上。这就是为什么答案要看倒数两个状态而不是最后一个状态。很多第一次做的人在这里绕不过弯，总觉得到顶之前必须踩完所有台阶，其实题目从来没这么要求过。

4.2 用[1,100,1,1,1,100,1,1,100,1]推一遍

这道题还有一个非常经典的“陷阱用例”：cost=[1,100,1,1,1,100,1,1,100,1]，正确答案是6。我建议每个人都亲手推一遍，推完你对“跳过昂贵台阶”会理解得特别深。

按定义A一步步算：

• dp[0] = 1
• dp[1] = 100
• dp[2] = min(100, 1) + 1 = 2（从0跳到2）
• dp[3] = min(2, 100) + 1 = 3
• dp[4] = min(3, 2) + 1 = 3（从2跳到4）
• dp[5] = min(3, 3) + 100 = 103（这里被100狠狠卡了一下）
• dp[6] = min(103, 3) + 1 = 4（从4跳到6，绕开了下标5的100）
• dp[7] = min(4, 103) + 1 = 5
• dp[8] = min(5, 4) + 100 = 104（又被100卡一次）
• dp[9] = min(104, 5) + 1 = 6
• 答案 = min(dp[8], dp[9]) = min(104, 6) = 6

看着dp[5]=103和dp[8]=104这两个大数字就明白了一件事：贪心或者无脑走一步，很容易踩到那些100块的台阶；而动态规划通过“从dp[4]跳到dp[6]”这种操作，直接把100块的大坑跳过去了。这也是为什么这类题必须用DP而不是贪心。

4.3 手推过程中最容易产生的错觉

手推时最容易产生的错觉是“dp[i]必须包含到达顶部之后的状态”。实际上递推公式里每次加的是cost[i]，也就是踩台阶的钱。顶部是虚拟位置，不收费。

另一个常见错觉是“起步免费”。不少人在初始化时写dp[0]=0，觉得还没开始走就不该付钱。但题目明确说了可以从下标0或者1起步，你选哪一级起步，那一级的过路费就必须交。所以dp[0]=cost[0]而不是0。这个细节在[10,15,20]里还不明显，换成[1,100,1,1,1,100,1,1,100,1]这种用例，初始化写错直接会导致最终答案偏差。

5. 和爬楼梯问题放一起看：DP的两大题型一次理顺

5.1 计数型DP：第70题的爬楼梯

刷到这道题的人多半刚做过或者马上会做到第70题“爬楼梯”。那道题问的是“有多少种不同的方法爬到楼顶”，递推公式是f[i] = f[i-1] + f[i-2]，初值一般取f[1]=1、f[2]=2。它求的是方案总数，不是最小花费。同样是“一次走一级或两级”的规则，一个是把所有方案加起来，一个是把所有花费取最小值，这就构成了动态规划里非常典型的两大题型：计数型DP和最值型DP。

把两道题放在同一天做，效果比单独刷十道都强。因为它们的差别恰好集中在两个地方：递推公式一个是加法一个是min，初始化和返回值一个看总数一个看最小花费。对比着记，比死记硬背模板有效得多。

5.2 一张表看清两道题的差别

它们还有一个共同点：都只需要看前两个状态，所以都可以用滚动数组优化到O(1)空间。学会滚动数组之后，这两道题的代码都会短一大截。

5.3 举一反三：改写成最大收益、可跳K步、打印路径

如果把“最小花费”改成“最大收益”，比如每个台阶上有金币，问你最多能捡多少钱到顶，处理方式几乎不变，把min换成max就行，初值要把“负收益”的可能性考虑进去，比如某个台阶是陷阱要扣钱，那你可能选择不踩它。

如果把“一次走1级或2级”改成“一次最多走K级”，递推就要改成内层循环：dp[i] = min(dp[i-1], dp[i-2], ..., dp[i-K]) + cost[i]，时间复杂度会变成O(nK)，但思路完全一样。面试时遇到这种变形，先别慌，认出是同一道题换个壳就行了。

还有一个很有意思的扩展：打印具体路径。做法是额外开一个pre数组，记录每个dp[i]到底是从i-1还是i-2转移过来的，算完dp之后从最后一步倒着回溯，就能把最优路线一步一步还原出来。这个能力在面试里属于加分项，但前提是把基础版本的状态定义吃透。

6. 第37天总结：这道题给我留下的三个提醒

6.1 先写注释，再写代码

这道题让我最深的体会是：动态规划最难的往往不是递推公式本身，而是状态定义在脑子里是模糊的。以前我经常写完代码跑一遍报错，然后对着屏幕发呆，最后发现是dp[i]的定义和初始化对不上。

现在的做法是，任何DP题动笔之前先在编辑器里敲一行注释，把这四件事固定下来：状态含义、递推公式、初始化、返回什么。这行注释就像施工图纸，代码只是照着图纸搭积木。第37天回头看，这个习惯帮我省下的调试时间，比多刷十道题还有用。

6.2 边界情况单独测

n=1和n=2这两个边界，我在练习时吃过不少亏。n=1时只有一级台阶，直接返回cost[0]；n=2时答案是min(cost[0], cost[1])。代码里dp[1]的赋值在n=1时会越界，所以养成习惯：先判长度，再开数组。面试官很喜欢在这种地方挖坑，因为大多数人会把主要逻辑写完就交，完全想不到边界。

我自己整理了一份这道题的“自测清单”，每次写完直接往里套：

• [10,15,20]，期望10；
• [1,100,1,1,1,100,1,1,100,1]，期望6；
• [10]，期望10；
• [10,15]，期望10；
• [0,0,0]，期望0。

如果这些用例都能一次通过，这道题基本就稳了。

6.3 滚动数组的更新顺序要刻进肌肉记忆

滚动数组的代码看上去很短，但“先更新哪个变量”这件事，写错一次就要花很久排查。我的办法是先写出完整数组版本，跑通之后再压缩成滚动版本，压缩时每一步都对照着完整版检查一遍。对于初学者，我特别不建议一上来就直接写滚动数组，因为你对状态本身还不熟，压缩之后更难定位问题。先把O(n)版本写对，再谈优化，这才是稳的路子。

还有一个第37天刷题节奏上的心得：动态规划题做一遍是不够的，最好隔几天回来重做，而且重做时不要看旧代码，直接空手写。写完之后再对照自己之前的注释，看看状态定义有没有变得更清晰。这道746题我前前后后写了四遍，每一遍都比上一遍少花时间，第四遍已经能闭着眼睛把滚动数组写出来。刷题计划的进度到了中段，比的已经不是“见过多少题”，而是“有多少题能真正脱离答案独立写出来”。凡是能用这道题把状态定义、递推公式、初始化、遍历顺序这四个动作一气呵成的人，后面遇到再复杂的DP题，心里都会更有底。