使用最小花费爬楼梯 图解题解

这道题到底在求什么

给一个数组 cost，下标 i 处的值是「离开第 i 阶」要付的钱。你可以从第 0 阶或第 1 阶起步（起步不花钱），每次向上走 1 阶或 2 阶，目标是花最少的钱爬到楼顶。这里有个最容易踩的坑：楼顶不收费。cost 只到最后一阶，站上楼顶不再「离开」任何台阶，所以不计费，答案是 dp[n] 而非 dp[n-1]。

为什么贪心每步挑便宜的会错

一个很自然的想法是贪心：每步都跳到眼前更便宜的那阶。但眼前省下的这一步，往往把你顶到后面只剩高价阶可踩。以 cost = [1,100,1,1,1,100,1,1,100,1] 为例，那几个 100 就是专门埋来惩罚短视选择的陷阱。

把所有路径枚举一遍当然不会错，但每步两个分支一路分叉，路径数随阶数指数膨胀，根本算不完。出路是记住「到每一阶的最小花费」，让后面的决策直接复用，而不是每次从头再拼。

dp 怎么定义，起步为什么是 0

定义 dp[i] 为「爬到第 i 阶所需的最小花费」。起点铺两个：dp[0] = 0、dp[1] = 0，因为题目允许从第 0 或第 1 阶零成本起步。要分清两件事——踏上某阶不花钱，离开某阶才按 cost 付费。所以「到第 i 阶」的花费只算一路上离开过的台阶费用，落脚的第 i 阶还没离开，不计。

转移为什么是两条来路取 min

站在第 i 阶回头看，上一步只可能来自两处：从第 i-1 阶走 1 阶上来，代价是「到 i-1 阶的最小花费」再加上离开它的 cost[i-1]；或者从第 i-2 阶跨 2 阶上来，代价是「到 i-2 阶的最小花费」加 cost[i-2]。两条来路各自的最优都是子问题已经算好的，到第 i 阶的最优就是两者取更小：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。

拿题目样例把表填出来

对着 cost = [1,100,1,1,1,100,1,1,100,1] 亲手填一遍最有感觉。起步 dp[0]=0、dp[1]=0。到第 2 阶：从第 1 阶来花 0+100=100，从第 0 阶跳 2 阶来花 0+1=1，取小的 dp[2]=1——第一个 100 就这样被绕开。接着 dp[3]=min(1+1, 0+100)=2，同法逐格上推，到 dp[9]=min(4+100, 4+1)=5、dp[10]=min(5+1, 4+100)=6，楼顶花费 6，正是答案。

复杂度与三个翻车点

从第 2 阶线性推到第 n 阶，每格只做一次比较，时间 O(n)；dp[i] 只依赖前两项，用两个变量滚动即可，空间 O(1)。

三个高频错处：一是给楼顶也付了费，可楼顶根本不收费，答案是 dp[n]；二是起步费设错，dp[0] 和 dp[1] 都该是 0；三是付错台阶——走到第 i 阶付的是「来路那一阶」的 cost（cost[i-1] 或 cost[i-2]），不是 cost[i]。

Python

def minCostClimbingStairs(cost):
    n = len(cost)
    a, b = 0, 0   # dp[i-2], dp[i-1]
    for i in range(2, n + 1):
        a, b = b, min(b + cost[i-1], a + cost[i-2])
    return b

C++

int minCostClimbingStairs(vector<int>& cost){
    int n = cost.size(), a = 0, b = 0;
    for(int i = 2; i <= n; ++i){
        int c = min(b + cost[i-1], a + cost[i-2]);
        a = b; b = c;
    }
    return b;
}

Java

int minCostClimbingStairs(int[] cost){
    int n = cost.length, a = 0, b = 0;
    for(int i = 2; i <= n; i++){
        int c = Math.min(b + cost[i-1], a + cost[i-2]);
        a = b; b = c;
    }
    return b;
}