Min Cost Climbing Stairs

題目描述

給定整數陣列 cost，cost[i] 是踩上第 i 階的費用。可從第 0 或第 1 階開始，每次爬 1 或 2 階。到達陣列長度以外即為頂樓。回傳最小費用。

輸入：cost = [10,15,20]
輸出：15
解釋：從第 1 階開始（費用 15），跨兩階到頂樓

輸入：cost = [1,100,1,1,1,100,1,1,100,1]
輸出：6

解題思路

定義狀態

dp[i] = 踩到第 i 階（含付費）的最小累計費用

初始條件

dp[0] = cost[0], dp[1] = cost[1]。可以從第 0 或第 1 階起步，起步時付該階費用

轉移方程

dp[i] = cost[i] + min(dp[i-1], dp[i-2])。例如 cost=[10,15,20] → dp[2] = 20 + min(15,10) = 30

空間優化

dp[i] 只依賴 dp[i-1] 和 dp[i-2]，用 prev1 和 prev2 兩個變數滾動替代整個陣列

答案

min(prev1, prev2)：頂樓在 index n（陣列外），可以從 n-1 跨 1 步或 n-2 跨 2 步抵達

程式碼

C#

csharp

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int prev2 = cost[0]; // dp[i-2]
        int prev1 = cost[1]; // dp[i-1]
        
        for (int i = 2; i < n; i++) {
            int curr = cost[i] + Math.Min(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }
        return Math.Min(prev1, prev2);
    }
}

TypeScript

typescript

function minCostClimbingStairs(cost: number[]): number {
    let prev2 = cost[0];
    let prev1 = cost[1];
    
    for (let i = 2; i < cost.length; i++) {
        const curr = cost[i] + Math.min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return Math.min(prev1, prev2);
}

Python

python

def minCostClimbingStairs(cost: list[int]) -> int:
    prev2, prev1 = cost[0], cost[1]
    
    for i in range(2, len(cost)):
        curr = cost[i] + min(prev1, prev2)
        prev2, prev1 = prev1, curr
    
    return min(prev1, prev2)

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

Time：只做一次線性遍歷，每步常數操作
Space：用兩個滾動變數取代 dp 陣列，O(1)

圖解

階梯 0 (cost[0])

跨2階→

階梯 1 (cost[1])

跨1階→

階梯 2

跨1階→

頂樓

圖表展示了到達每一階的兩種來源：從前一階跨 1 步，或從前兩階跨 2 步。最終到達頂樓也有兩條路（從 n-1 或 n-2），取較小成本即為答案。

進階觀點

💡面試追問

為什麼答案是 min(dp[n-1], dp[n-2])？ 頂樓的位置是 index n（在陣列最後一個元素的右邊），從 n-1 跨 1 步或 n-2 跨 2 步都能到達頂樓。兩者取較小成本。如果直覺地只回傳 dp[n-1]，會漏掉從 n-2 直接跨兩步跳過 n-1 的更優路線。
和 70. Climbing Stairs 的關係？ Climbing Stairs 計算「方案數」用加法（dp[i] = dp[i-1] + dp[i-2]），本題計算「最小成本」用 min。兩者的 DP 結構完全相同，只是聚合函數不同。
可以改成最大成本嗎？ 可以，只要把 min 全部換成 max。DP 框架不變，這展示了 DP 的通用性——改變目標函數不影響結構。

邊界情況

cost 長度為 2：只有兩階，從第 0 或第 1 階直接跳到頂樓，答案 = min(cost[0], cost[1])
所有 cost 值相同：不管怎麼走成本都一樣，答案 = ceil(n/2) × cost（盡量跨兩步最省）
cost 值為 0：部分階梯免費，DP 仍正確處理，免費的階梯自然被優先選擇

理解測驗

🤔 為什麼最終答案是 min(prev1, prev2) 而不只是 prev1？

🤔 這題的狀態轉移方程 dp[i] = cost[i] + min(dp[i-1], dp[i-2]) 中，為什麼要加 cost[i]？