LeetCode LCR 088. 使用最小花费爬楼梯
题目描述
题意分析
每级台阶有对应费用，支付后可以向上走一级或两级，起点可选下标零或一。数组长度为
n时，楼顶位于数组之外的下标n，目标是到达楼顶的最小总花费。为了统一起点和终点的处理，可以把台阶费用记到“从这一级向上走”的转移中。起点的到达费用为零，并不意味着起点台阶免付费；真正离开它时仍要计入对应的
cost。
解法：按到达台阶定义 DP
核心思路
[!blue]
dp[i]表示到达位置i、尚未计入当前台阶费用时的最小花费，下标范围是0到n。到达同一位置后，可走的后续路线完全相同，因此只需保留此前累计费用最小的路线。到达
i的最后一步只有两种来源：从i-1走一级，或从i-2走两级。离开出发台阶时要支付它的费用，所以两个候选分别是dp[i-1] + cost[i-1]和dp[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，由数组默认值给出。从
i = 2正序计算到n，两个依赖状态都已求出。到楼顶的转移只会读取cost[n-1]或cost[n-2]，不用也不能访问cost[n]；最终的dp[n]已计入最后一个实际经过台阶的费用。
解题步骤
- 创建长度为
n+1的状态数组，包含楼顶位置，前两个状态保持零。- 从位置二开始，分别计算由前一级和前两级到达的费用，保存最小值。
- 一直递推到楼顶下标
n，返回dp[n]。
代码实现
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)$，每个位置只计算两个候选费用。
- 空间复杂度：$O(n)$，保存
n+1个状态；转移只依赖前两个值，也可以进一步压缩为常数空间。
关键点总结
[!green]
- 当前状态尚未支付所在台阶的费用，转移中要加出发位置的
cost，不能中途改成“已经支付”的口径。- 两个起点的到达费用为零，起点台阶自身的费用会在第一次向上走时计入。
- 答案位置是数组之外的
n；只有两级台阶时，递推自然得到两个起点费用的较小值。
易错点总结
[!yellow]
- dp[i] 表示到达台阶 i 尚未支付该级费用；转移要加出发台阶的 cost。
- 起点可选 0 或 1，两者初始到达费用为 0；目标是楼顶下标 n。
- 若改成已支付当前台阶的状态，初始化、转移和返回值都要一起改变，不能混搭。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 同样从前一或前两阶转移，原题统计走法，本题取最低费用。 |
| 198. 打家劫舍 | 中等 | 同样是线性DP并能滚动压缩，原题最大化不相邻收益，本题选择走一阶或两阶的最低代价。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！