LeetCode 746. 使用最小花费爬楼梯

约 4 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 LeetCode 75 腾讯 字节 虾皮
标签
数组 动态规划

题目描述

✅ 746. 使用最小花费爬楼梯

image-20260928224712084

image-20260928224712086

题意分析

cost[i] 是站在第 i 级台阶后、继续向上走之前需要支付的费用，支付后可以向上走一级或两级。可以直接从第零级或第一级开始，求到达楼顶所需的最少总费用。

楼顶是数组之外的第 n 个位置，不是最后一个有费用的台阶 n - 1。允许跨过未踩到的台阶，因此不必支付所有费用；题目只求最小金额，不需要返回经过的台阶序列。

解法：滚动 DP

核心思路

[!blue]

定义 dp[i] 为到达位置 i、还没有支付当前位置费用时的最小累计花费。起点可以自由选择第零级或第一级，所以 dp[0] = dp[1] = 0；这不表示这两个台阶永远免费，而是它们的费用在离开时才加入。

到达位置 i 的最后一步只有两个来源：从 i - 1 走一级，需要 dp[i - 1] + cost[i - 1]；或者从 i - 2 走两级，需要 dp[i - 2] + cost[i - 2]。这两种情况覆盖所有合法走法，分别使用到达前驱的最小代价后再取较小值，得到当前位置的最优费用。

转移只需要前两个状态，可以用 prev2、prev1 滚动保存。处理位置 i 之前，它们分别表示 dp[i - 2] 和 dp[i - 1]。先计算本轮 cur，再把旧 prev1 移到 prev2，把 cur 放到 prev1，为下一位置保留正确状态。

循环必须计算到 i = n。这一轮支付的是最后两种可能前驱的台阶费用，楼顶本身没有费用，也不会读取不存在的 cost[n]。处理完后，prev1 就是顶部位置的最小累计花费。

解题步骤

  1. 初始化 prev2 = 0、prev1 = 0，对应两个可选起点的到达费用。
  2. 从位置 2 依次计算到位置 n。
  3. 每轮比较 prev1 + cost[i - 1] 与 prev2 + cost[i - 2]，较小值记为 cur。
  4. 按顺序执行 prev2 = prev1、prev1 = cur，保留下一轮需要的历史状态。
  5. 返回最终 prev1。

代码实现

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;

        // 顶部在数组之外的 n 位置，也必须完成这一轮转移
        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

    // 顶部在数组之外的 n 位置，也必须完成这一轮转移
    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)$，每个位置做一次常数时间转移。
  • 空间复杂度：$O(1)$，只保存前两个位置和当前结果。

关键点总结

[!green]

  • 状态把费用记在离开前驱时，初始化和转移都必须与此约定一致。
  • 两个起点到达费用为零，选择从哪一级开始已包含在动态规划中。
  • 楼顶位置 n 需要计算，但不存在 cost[n]，只支付对应前驱费用。
  • 先算新值再移动旧值，避免丢失相隔两级的前驱状态。

易错点总结

[!yellow]

  • 只计算到 n - 1，得到的是到达最后一个台阶的费用，并未到达顶部。
  • 初始化第二个起点为第零级费用，会强制经过第零级，遗漏直接从第一级开始的方案。
  • 转移时加 cost[i]，混淆了状态的支付时机，也会在顶部下标越界。
  • 先覆盖前一状态再复制给前二状态，会使下一轮读到两份相同的新值。

相似题目

题目 难度 关联与区别
70. 爬楼梯 简单 同样从前一或前两阶转移，原题统计走法，本题取最低费用。
198. 打家劫舍 中等 同样是线性DP并能滚动压缩，原题最大化不相邻收益，本题选择走一阶或两阶的最低代价。
91. 解码方法 中等 按最后一段长度递推前缀方案数；本题转为达到当前台阶的最小费用，该题最后编码可占一位或两位。
1137. 第 N 个泰波那契数 简单 按最后一段长度递推前缀方案数；本题转为达到当前台阶的最小费用，该题依赖前三个状态。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/42745447
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！