LeetCode LCR 088. 使用最小花费爬楼梯
目录
题目描述
题意分析
给一个数组
cost，cost[i]是站在第i级台阶上要支付的费用。付费之后可以往上爬一级或两级。可以从下标 0 或下标 1 出发（出发本身不额外收费，但站上去要付该级的费用），目标是走到楼梯顶部，也就是下标n这个「第 n 级」——它在数组之外，因此不需要付费。求最小总花费。
这里最容易读错的是费用的计费点。
cost[i]是离开第i级时支付的，或者说是「踩上第i级并从它继续往上」的代价。终点n不在数组里，所以永远不付费；反过来，最后一级cost[n-1]是否要付，取决于路线是否踩过它——从n-2一步跨到n就绕开了它。这解释了为什么答案常常小于数组末尾若干项之和。
每一步只有「爬一级」「爬两级」两种选择，说明到达某一级的方式只能来自它前面的两级，问题具有一维、局部、无后效性的递推结构。同时题目只要最小花费这一个数值，不要具体路线，因此不必枚举方案，直接沿台阶递推即可。
约束：
2 ≤ cost.length ≤ 1000，0 ≤ cost[i] ≤ 999。数组至少两个元素，所以不存在「一步都不用走」的退化情况。费用非负这一点保证了不会出现「多绕几步反而更省」的反直觉解，最优路线一定是单向向上的。边界重点在两个起点都免费这条规则如何编码，以及答案取的是「到达n」而不是「到达n-1」。
解法：动态规划递推
核心思路
暴力做法是从两个起点出发做搜索，每级分岔成两条路，路线总数呈斐波那契级增长，
n = 1000时天文数字。瓶颈在于「到达第i级的最小花费」这个子问题被不同的前缀路线反复计算了无数遍。
关键观察是：站在第
i级时，之前具体走过哪条路线对后续毫无影响，唯一有用的信息是「走到这里累计花了多少」。既然如此，对每一级只保留最小值即可，子问题数量从指数级塌缩到n + 1个。
于是定义状态：
dp[i]表示到达第i级台阶（尚未支付cost[i]）所需的最小总花费，i的取值范围是0到n。这个定义里「尚未支付cost[i]」是精髓——它让终点dp[n]的语义天然正确（第n级不存在费用），也让转移写起来对称。
转移方程：到达第
i级只能从第i-1级迈一步、或从第i-2级迈两步。从第i-1级出发要先付cost[i-1]，从第i-2级出发要先付cost[i-2]，于是
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
基准情形直接由题意给出：
dp[0] = dp[1] = 0，因为从下标 0 或下标 1 出发都不额外收费，站上去时还没付钱。这两个 0 恰好是数组的默认初值，所以代码里连显式赋值都省了。
答案是
dp[n]，不是dp[n-1]，也不是min(dp[n-1], dp[n-2])——后者是把「顶部」误解成最后一级台阶的典型错误。
解题步骤
- 开长度为
n + 1的数组：状态下标要覆盖到n，因为终点是数组之外的那一级。开成n会直接漏掉答案所在的格子。
- 基准情形依赖默认零值：
dp[0]与dp[1]都是 0，含义是「站在起点上、还没付钱」。Java 的new int[]与 Go 的make([]int, ...)都会零初始化，所以不需要额外写。理解它们为什么是 0，比背下来更重要。
- 从
i = 2开始正序递推：dp[i]依赖下标更小的dp[i-1]和dp[i-2]，所以必须正序，且起点是 2——i = 0和i = 1是基准，i从 0 开始会访问dp[-1]越界。
- 转移时把费用记在「出发的那一级」上：
dp[i-1] + cost[i-1]而不是dp[i-1] + cost[i]。费用属于被踩过的台阶，不属于目的地；写成cost[i]在i == n时还会直接越界。
- 返回
dp[n]：循环结束时dp[n]已经算好，直接返回。
以
cost = [10, 15, 20]走一遍，n = 3，dp长度为 4。
初始
dp = [0, 0, 0, 0]，其中前两个 0 是基准：从下标 0 出发花费 0，从下标 1 出发也花费 0。
i = 2：dp[1] + cost[1] = 0 + 15 = 15，表示从下标 1 起步、付 15 后迈一级到达 2；dp[0] + cost[0] = 0 + 10 = 10，表示从下标 0 起步、付 10 后迈两级到达 2。取小得dp[2] = 10。
i = 3：dp[2] + cost[2] = 10 + 20 = 30，表示走到第 2 级再付 20 迈一级到顶；dp[1] + cost[1] = 0 + 15 = 15，表示从下标 1 起步付 15 后直接迈两级跨到顶部，绕开了cost[2]。取小得dp[3] = 15。
返回
dp[3] = 15，对应路线「从下标 1 出发 → 付 15 → 跨两级到顶」。这个用例很好地说明了为什么答案不是dp[n-1]：dp[2] = 10看起来更小，但它只走到第 2 级，还没到顶，从那里到顶还要再付 20。
再以
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]快速核对：dp依次为0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6，答案dp[10] = 6，对应路线是踩下标 0、2、3、4、6、7、9 各付 1，共 6，与预期一致。
代码实现
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// dp[i]：到达第 i 级（尚未支付 cost[i]）的最小花费；下标要覆盖到 n。
int[] dp = new int[n + 1];
// dp[0] = dp[1] = 0：从下标 0 或 1 出发都不额外收费，默认零值即可。
for (int i = 2; i <= n; ++i) {
// 费用记在出发的那一级上，所以是 cost[i - 1] 与 cost[i - 2]。
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
func minCostClimbingStairs(cost []int) int {
n := len(cost)
// dp[i]：到达第 i 级（尚未支付 cost[i]）的最小花费；下标要覆盖到 n。
dp := make([]int, n+1)
// dp[0] = dp[1] = 0：从下标 0 或 1 出发都不额外收费，默认零值即可。
for i := 2; i <= n; i++ {
// 费用记在出发的那一级上，所以是 cost[i-1] 与 cost[i-2]。
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O(n)$，从 2 到
n只扫一遍，每格做一次加法和一次取最小，都是常数操作。- 空间复杂度：$O(n)$，用了长度为
n + 1的数组。由于dp[i]只依赖前两格，可以用两个变量滚动把空间压到 $O(1)$；这里保留完整数组是为了让状态定义一目了然，面试中主动指出可优化到常数空间是加分项。
关键点总结
- 状态定义里「费用算在谁头上」必须一次讲清楚：本题采用「到达第
i级但尚未支付cost[i]」，于是转移里出现cost[i-1]与cost[i-2]，终点dp[n]自然免费。定义换成「已支付」也能做，但转移和边界要跟着全改——不要中途换定义，这是 DP 出错最常见的根源。- 答案取
dp[n]而非dp[n-1]，因为楼梯顶部在数组之外。凡是题目里出现「顶部」「终点」这类数组之外的位置，都要先确认状态数组要不要多开一格。- 基准情形要能用题意解释，而不是试出来的：两个起点免费，所以
dp[0] = dp[1] = 0。面试时能说出「为什么是 0」比写对更重要。- 递推方向由依赖关系决定：
dp[i]依赖更小的下标，因此正序；这条规则在所有线性 DP 中通用，也是后面滚动数组能否原地更新的判据。- 可迁移的识别信号：「每一步只能从固定的前几个位置转移过来，且只要最优值不要方案」，就是一维线性 DP 的典型形态，爬楼梯、打家劫舍、跳跃游戏都属于这一族。
易错点总结
- 数组开成
new int[n]：cost = [10,15,20]时循环写到i = n会数组越界抛异常。- 返回
dp[n-1]：cost = [10,15,20]会返回dp[2] = 10，但正确答案是 15，因为只走到了第 2 级还没到顶。- 返回
min(dp[n-1], dp[n-2])：cost = [10,15,20]返回min(10, 0) = 0，把「站在起点」当成了到顶。- 转移写成
dp[i-1] + cost[i]：i = n时cost[n]越界；即使把上界改小，cost = [10,15,20]也会算出dp[2] = min(0+20, 0+15) = 15这种把费用记到目的地的错误值。- 循环从
i = 0或i = 1开始：会访问dp[-1]或cost[-1]，直接越界。- 误把
dp[0]设成cost[0]、dp[1]设成cost[1]：cost = [10,15,20]得到dp[2] = min(15+15, 10+10) = 20、dp[3] = min(20+20, 15+15) = 30，答案翻倍。- 把状态定义成「站在第
i级且已付费」却仍写cost[i-1]：cost = [1,100]会算出 0 而不是 1，两套定义混用是 DP 最隐蔽的错误。- 以为可以贪心地每步选较小的下一级：
cost = [0, 0, 100, 0, 0]时贪心会在某一步被 100 挡住绕不开，而 DP 能选出跨越它的路线；贪心在这类「局部最小不等于全局最小」的题上必错。- 滚动数组优化时把两个变量的更新顺序写反：
cost = [10,15,20]若先更新pre再更新cur，第二轮会用到被覆盖的值，结果偏小。- 误以为费用非负就可以不比较、总走一步：
cost = [1,100,1,1]时一步一步走要付1+100+1 = 102，而跨过 100 只需 2，必须真的取最小值。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 746. 使用最小花费爬楼梯 | 简单 | 与本题完全同题，代码可原样提交 |
| 70. 爬楼梯 | 简单 | 没有费用，求方案数而非最小值，min 换成加法即成计数递推 |
| 509. 斐波那契数 | 简单 | 同一条递推式的纯数学形态，是本题去掉一切题面包装后的骨架 |
| 剑指 Offer 10- I. 斐波那契数列 | 简单 | 与 509 同题，额外要求对 1e9+7 取模，考察溢出处理 |
| 剑指 Offer 10- II. 青蛙跳台阶问题 | 简单 | 与 70 同题，基准值定义略有差异，容易在 n = 0 上翻车 |
| 面试题 08.01. 三步问题 | 简单 | 每步可跨 1、2、3 级，转移项从两项扩到三项，同样要注意取模 |
| 198. 打家劫舍 | 中等 | 同为一维线性 DP，但约束从「步长」变成「相邻不可同时选」 |
| 补充题 2. 圆环回原点问题 | 中等 | 状态多一维「当前所在位置」，转移在环上左右两个方向计数 |