746. 使用最小花费爬楼梯
题目描述
输入整数数组 cost，长度为 n。站在第 i 级台阶上时，支付 cost[i] 后可以向上走 1 级或 2 级。
起点可以选第 0 级或第 1 级，选起点本身不花钱。楼顶是下标为 n 的位置，即越过最后一级台阶。
返回到达楼顶所需的最小总花费。
示例 1
输入：cost = [10,15,20] 输出：15
解释：从第 1 级起步，付 15 直接跨两级到楼顶。
示例 2
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6
解释：从第 0 级起步，一路避开花费为 100 的台阶，共付 6 次 1。
数据范围
2 <= cost.length <= 10000 <= cost[i] <= 999
解题思路
设 dp[i] 为到达第 i 级（还没付第 i 级的费用）的最小花费。到达 i 只有两种来路：从 i-1 付 cost[i-1] 爬一级，或从 i-2 付 cost[i-2] 爬两级，取较小者。起点可以任选 0 或 1，所以 dp[0] = dp[1] = 0。
为什么正确
循环到 i 时，dp[0..i-1] 都已是到达对应台阶的最小花费。
复杂度分析
时间 O(n)，空间 O(n)（只保留两个变量可降到 O(1)）。
易错点
楼顶是下标 n，不是 n-1。返回 dp[n-1] 或 min(cost) 都会出错。另外要付的是“离开的那级”的费用 cost[i-1] / cost[i-2]，不是 cost[i]。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[n]class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1, 0);
for (int i = 2; i <= n; i++) {
dp[i] = 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 := make([]int, n+1)
for i := 2; i <= n; i++ {
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}var minCostClimbingStairs = function(cost) {
const n = cost.length;
const dp = new Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
};function minCostClimbingStairs(cost: number[]): number {
const n = cost.length;
const dp = new Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}