跳转至

746. 使用最小花费爬楼梯（Min Cost Climbing Stairs）

频次 ★★★ · 难度 🟢 · 高频：字节

题目

数组 cost[i] 表示从第 i 阶向上爬的花费，可从第 0 或第 1 阶开始，每次爬 1 或 2 阶，求到达楼顶的最小总花费。

示例： 

输入: cost = [10,15,20]
输出: 15  （从第 1 阶开始，爬 2 阶到顶，花费 15）

思路

DP：dp[i] 表示到达第 i 阶的最小花费。 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

楼顶在数组末尾的下一个位置，即 dp[n] 是答案。可优化到 O(1) 空间（两个变量滚动）。

代码

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int a = 0, b = 0;              // dp[0], dp[1]（从 0 或 1 开始，花费为 0）
    for (int i = 2; i <= n; i++) {
        int c = Math.min(a + cost[i - 2], b + cost[i - 1]);
        a = b;
        b = c;
    }
    return b;
}

到达付 / 离开付：两种流派与虚拟楼顶返回值

流派甲：到达付 流派乙：离开付（wiki 参考解）
dp[i] 语义 踩上 i 且付过 cost[i] 的最小总费 已越过 i（在 i 处付完、准备上爬）的最小总费
初始化 dp[0]=cost[0], dp[1]=cost[1] dp[0]=0, dp[1]=0（站 0/1 免费）
转移 dp[i] = cost[i] + min(dp[i-1], dp[i-2]) dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
答案 min(dp[n-1], dp[n-2]) dp[n]（数组开 n+1，楼顶是虚层、cost 不付）

两流派输出恒等、代码全队形不同（错位一档）——选定后初始化/循环/返回值全套一致，别中途换。

常见 WA（实测踩坑）：返回 dp[n-1]

到达付流派下返回 dp[n-1] 只算了"最后 Konto at last"的路径，漏掉"从 last-1 直跳上楼"——楼顶是虚拟层，最后一跳免费。修正后 [10,15,20]: 30✗ → 15✓、[1,100]: 100✗ → 1✓。且对有些用例碰巧相等（dp[last] 恰是 min），随机挂正因此。

复杂度

  • 时间：O(n)
  • 空间：O(1)

边界条件

  • cost 长度 2：直接取 min(cost[0], cost[1])
  • 从 0 或 1 开始不花钱——dp[0]=dp[1]=0

变式

  • 70. 爬楼梯：不带 cost 的版本，dp[i]=dp[i-1]+dp[i-2]
  • 三步问题：每次可爬 1~3 阶，dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

易错点

  • 楼顶在 cost.length 位置（不是 cost.length - 1），dp 数组长度为 n+1
  • dp[0] 和 dp[1] 初始化为 0（站在起点不花钱，花费用在"离开"时）

面试追问

  • 如果花费在"到达"而不是"离开"？ 转移方程会变，讨论清楚题意再写

关联题