LeetCode 746. 使用最小花费爬楼梯
目录
题目描述
题意分析
给定数组
cost，cost[i]是站在第i级台阶上要支付的费用。付完这笔钱之后，可以往上走一级或两级。起点可以自选：从下标 0 开始，或者从下标 1 开始。目标是走到「楼梯顶部」，也就是下标n这个位置（它在数组之外，不存在费用），求最小总花费。这段描述里最容易读错的是费用的归属时机。费用是「离开某级台阶时付」，不是「到达某级台阶时付」。所以起点那一级也要付钱，而终点
n不在数组内，永远不付钱。把这一点读反，最后一步会多算或少算一笔。「每次只能走 1 步或 2 步」这条约束是最强的信号：它意味着能到达位置
i的前驱只有i-1和i-2两个，且不存在任何绕路——从下面上来的路径永远不会回头。也就是说，到达i的最优解只由到达i-1和i-2的最优解决定，与更早的历史完全无关。这是典型的最优子结构加无后效性，正是可以用递推逐级求解的依据。「起点二选一」这条约束同样重要：站上第 0 级和站上第 1 级都不需要预先付出任何代价，费用只在离开时才产生。所以两个起点的初始花费都是 0，不需要在其中做取舍——取舍会在后续递推里自动完成。
数据规模上，数组长度在 2 到 1000 之间，费用不超过 999。规模极小，效率不是考点，考点在于状态定义是否准确、边界是否对齐。值得注意的是长度至少为 2，所以不必担心只有一级台阶的退化情形。
边界有两处：位置 0 和位置 1 的花费都是 0（还没离开过任何台阶）；答案取的是位置
n而不是位置n-1，因为顶部在数组末尾再往上一级。
解法：滚动 DP
核心思路
先看暴力：从两个起点分别出发做深度优先搜索，每步枚举走 1 级还是 2 级，走到
n时结算总花费，取所有路径的最小值。它一定正确，但路径条数按斐波那契规模增长，$n = 1000$ 时是天文数字，必然超时。瓶颈在哪里？观察搜索树会发现，「从位置
i走到顶部的最小花费」被重复计算了指数多次——无论沿哪条路径走到i，从i往上的最优走法都是同一个，与怎么来的无关。这个观察就是无后效性：位置这一个量，已经足够概括到达此处后所有未来决策所需的全部信息。既然如此，每个位置只需要算一次，答案存下来复用即可。于是定义状态：
dp[i]表示「站到位置i上、但还没有支付cost[i]」时已经花掉的最少费用，其中i的取值范围是 $[0, n]$，dp[n]就是答案。这个定义里「还没支付当前级费用」这半句是全题的关键，它把费用的归属钉死在离开的那一刻，从而让终点n自然地不产生费用。转移由前驱唯一确定：能一步跨到
i的只有i-1（走一级）和i-2（走两级）。若从i-1来，代价是「站到i-1的花费」加上「离开i-1要付的cost[i-1]」；若从i-2来同理。取两者较小值，得到
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。初值
dp[0] = dp[1] = 0，对应「起点二选一且站上去不花钱」。注意dp[1] = 0不是从dp[0]转移来的——若按转移式算dp[1]会得到cost[0]，那就等于强制从 0 出发，把「可以直接从 1 出发」这个选项抹掉了。这也是本题最隐蔽的一处初始化陷阱。最后一层优化来自转移式的形态：
dp[i]只依赖前两项，中间结果一旦用过就再也不会被读取。因此不必开长度为n+1的数组，用两个变量prev2（代表dp[i-2]）和prev1（代表dp[i-1]）滚动即可，空间从 $O(n)$ 压到 $O(1)$。滚动过程要维持的不变量是：每轮循环开始时，prev1 == dp[i-1]且prev2 == dp[i-2]。
解题步骤
- 初始化
prev2 = 0、prev1 = 0，分别代表dp[0]和dp[1]。两个都取 0 而不是prev1 = cost[0]，是因为题目允许直接从下标 1 起步，站上去本身不花钱。- 循环从
i = 2开始。位置 0 和 1 已经由初值给出，从 2 起才有两个合法前驱，转移式才成立。- 循环条件写
i <= n而不是i < n。顶部是下标n，少算一轮就只走到了最后一级台阶上，答案会偏小（漏掉最后那一步的费用）。这是本题第一大边界错误。- 算
cur = min(prev1 + cost[i-1], prev2 + cost[i-2])。两项分别对应「从i-1迈一级过来」和「从i-2迈两级过来」，加的都是前驱那一级的费用而不是cost[i]——因为费用在离开时支付。- 滚动更新
prev2 = prev1，再prev1 = cur。顺序不能反：先写prev1 = cur会把旧的dp[i-1]冲掉，下一轮的prev2就变成了dp[i]，整条递推链错位一格。- 返回
prev1。循环结束时i刚越过n，此刻prev1恰好保存着dp[n]，即到达顶部的最小花费。返回prev2会得到dp[n-1]，即停在最后一级台阶上的花费，少走一步。以
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]（$n = 10$）走一遍。初始
prev2 = dp[0] = 0，prev1 = dp[1] = 0。
i = 2：min(dp[1] + cost[1], dp[0] + cost[0]) = min(0 + 100, 0 + 1) = 1，即dp[2] = 1（从 0 迈两级）。滚动后prev2 = 0、prev1 = 1。
i = 3：min(dp[2] + cost[2], dp[1] + cost[1]) = min(1 + 1, 0 + 100) = 2，dp[3] = 2。滚动后prev2 = 1、prev1 = 2。
i = 4：min(dp[3] + cost[3], dp[2] + cost[2]) = min(2 + 1, 1 + 1) = 2，dp[4] = 2（从 2 迈两级更划算）。
i = 5：min(dp[4] + cost[4], dp[3] + cost[3]) = min(2 + 1, 2 + 1) = 3，dp[5] = 3。
i = 6：min(dp[5] + cost[5], dp[4] + cost[4]) = min(3 + 100, 2 + 1) = 3，dp[6] = 3。
i = 7：min(dp[6] + cost[6], dp[5] + cost[5]) = min(3 + 1, 3 + 100) = 4，dp[7] = 4。
i = 8：min(dp[7] + cost[7], dp[6] + cost[6]) = min(4 + 1, 3 + 1) = 4，dp[8] = 4。
i = 9：min(dp[8] + cost[8], dp[7] + cost[7]) = min(4 + 100, 4 + 1) = 5，dp[9] = 5。
i = 10：min(dp[9] + cost[9], dp[8] + cost[8]) = min(5 + 1, 4 + 100) = 6，dp[10] = 6。循环结束返回
prev1 = 6。对应的实际走法是从下标 0 起步（付 1），跳到 2（付 1）、4（付 1）、6（付 1）、7（付 1）、9（付 1），再跨一步出界到顶部，合计 6，与答案吻合。若把循环写成
i < n，最后一轮停在i = 9，返回dp[9] = 5——那是「站在最后一级台阶上」的花费，还差最后一步没付，答案偏小。
代码实现
class Solution {
// 转移：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int prev2 = 0;
int prev1 = 0;
for (int i = 2; i <= n; i++) {
int cur = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}
func minCostClimbingStairs(cost []int) int {
// 转移：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
n := len(cost)
prev2, prev1 := 0, 0
for i := 2; i <= n; i++ {
cur := prev1 + cost[i-1]
if prev2+cost[i-2] < cur {
cur = prev2 + cost[i-2]
}
prev2 = prev1
prev1 = cur
}
return prev1
}
复杂度分析
- 时间复杂度：$O(n)$。循环从 2 跑到
n共 $n - 1$ 轮，每轮只做两次加法、一次取最小和两次赋值，全是常数操作，没有任何嵌套。- 空间复杂度：$O(1)$。凭的是转移式只回看两项——
dp[i]用完dp[i-2]之后它再无用处，所以用prev2、prev1两个整数滚动就能替代整张dp数组，与n无关。
关键点总结
- 状态定义要把「费用在什么时刻结算」写进去。本题定义成「站到位置
i且尚未支付cost[i]的最小花费」，才能让转移式加的是前驱的费用、让终点n天然免费；定义含糊，转移式一定会在末尾差一笔钱。- 「每步只能走 1 或 2 级」直接决定了前驱集合只有两个，这是斐波那契型递推的识别特征。看到「有限种步长、只能向前」就该往这类线性 DP 上想。
- 初值不能靠转移式反推。
dp[1] = 0是题目「起点二选一」赋予的独立信息，用转移式算会得到cost[0]，把一个合法起点悄悄删掉——凡是题目显式给了多个起点的 DP，初始化都要单独审一遍。- 转移只依赖固定个数的历史项时，一律可以滚动压缩到 $O(1)$ 空间；代价是失去了回溯具体路径的能力，如果题目改问「走了哪些台阶」就得留回完整数组。
- 面试视角：这题几乎必被追问三件事——「
dp数组开多长、为什么是n+1而不是n」「为什么两个初值都是 0」「能不能优化空间」。稳妥的答法是先写 $O(n)$ 空间的数组版把状态和边界讲清楚，再当场压成两个变量，顺带说明压缩后无法还原路径。上来就写滚动变量容易在边界上出错，也不便于向面试官展示推导过程。
易错点总结
- 循环写成
for (int i = 2; i < n; i++)：对cost = [10, 15, 20]只算到dp[2] = 10，返回 10，而正确答案是 15（从下标 1 起步付 15 直接跨到顶）。顶部是下标n，循环必须取到i == n。- 初值写成
prev1 = cost[0]：等于强制从下标 0 出发。对cost = [10, 15, 20]会算出dp[2] = min(10 + 15, 0 + 10) = 10、dp[3] = min(10 + 20, 10 + 15) = 25，返回 25 而不是 15。- 转移里加成
cost[i]：写成min(prev1, prev2) + cost[i]，i取到n时直接数组越界；即便循环只到n-1，费用也整体错位一级，cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]会得到 100 以上的结果。- 滚动顺序写反：先
prev1 = cur再prev2 = prev1，会让prev2和prev1变成同一个值。对cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]递推链整体错位，最终返回 106 之类的错误值。- 最后返回
prev2：返回的是dp[n-1]，即「停在最后一级台阶上」的花费。对cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]会返回 5 而不是 6，恰好少了最后一步的cost[9]。dp数组只开new int[n]：数组版里写int[] dp = new int[n]，访问dp[n]立刻抛ArrayIndexOutOfBoundsException；必须开n + 1长。- 误以为答案是
min(dp[n-1], dp[n-2])：把「顶部」理解成最后一级台阶。对cost = [10, 15, 20]会返回min(dp[2], dp[1]) = min(10, 0) = 0，显然荒谬——一步没走也算到顶。- 贪心地每步选较小的
cost：对cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]，局部最优会在中段被 100 卡住而绕不开，得到的总花费高于 6。步长选择的收益依赖后续台阶，无法逐步贪心决定。- 对长度为 2 的输入额外特判：题目保证
n >= 2，此时循环恰好跑一轮得到dp[2] = min(cost[1], cost[0])，结果正确；多写的特判分支反而常把min写成max或漏掉一侧。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 同样的两项递推，但求方案数用加法，起点唯一因而初值只有一种取法 |
| 509. 斐波那契数 | 简单 | 递推式的裸形态，没有费用和起点选择，可用来检验滚动变量的写法是否对齐 |
| 1137. 第 N 个泰波那契数 | 简单 | 前驱扩展到三个，滚动变量要从两个加到三个，更新顺序更易写错 |
| 面试题 08.01. 三步问题 | 简单 | 步长扩到 1/2/3 步且要求取模，考察大数溢出的处理 |
| 剑指 Offer 10- II. 青蛙跳台阶问题 | 简单 | 与 70 同构，额外要求对 $10^9+7$ 取模 |
| LCR 088. 使用最小花费爬楼梯 | 简单 | 与本题同题，可直接套用 |
| 198. 打家劫舍 | 中等 | 同为两项线性 DP，但约束从「步长」变成「不能选相邻」，转移取 max 且跳过一格 |
| 91. 解码方法 | 中等 | 结构相同的两项递推，但两个前驱各自带合法性判断，转移前要先验证字符能否成段 |