746. Min Cost Climbing Stairs

──────────────────────────────────────────────────────────────────────

每一階有一個花費，付了就能往上走 1 或 2 階。可以從第 0 階或第 1 階出發，問走到樓梯頂端（陣列尾端的再上一格）最少要付多少。

思路

這題是 70. Climbing Stairs 加上花費，但有兩個地方特別容易搞錯，都跟邊界的定義有關：

一、終點不是最後一階，是最後一階的「再上一格」。 陣列長度 n 的樓梯，終點是索引 n。所以站在最後一階時再走一步就到頂，不需要再付任何錢。

二、起點有兩個。 可以從第 0 階或第 1 階開始，所以答案是兩者取小，不是固定從 0 開始。

把這兩點想清楚，遞推式就很自然。定義：

dp(i) = 從第 i 階出發、走到頂端還要付的錢

那麼站在第 i 階就一定要付 cost[i]，然後往上 1 階或 2 階取小：

d p (i) = c o s t [i] + \min (d p (i + 1), d p (i + 2))

base case 是 dp(n) = 0（已經在頂端了）。答案是 min(dp(0), dp(1))。

和 198. House Robber 的差別值得對照：198 是「選或不選」（可以跳過某一格不付），這題是「一定要付當前這格，選擇的是下一步跨多遠」。狀態定義的方向不同，遞推式的形狀就不同。

解題方向

自頂向下

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
         
            @cache
            def dp(i):
                if i > len(cost):
                    return float('inf')
                if i == len(cost):
                    return 0
                curr = cost[i]
                return curr + min(dp(i + 1), dp(i + 2))
            
            return min(dp(0), dp(1))

@cache（functools.cache）一行就完成記憶化，不用自己維護字典 —— DP 最快的起手式就是「先寫暴力遞迴，再加 @cache」。

if i > len(cost): return float('inf') 是防止從 n-1 跨兩步跳過頭。其實從 n-1 跨兩步剛好到 n+1，那是「越過頂端」，用 inf 讓 min 自動淘汰它。也可以寫成 if i >= len(cost): return 0（把越過頂端也視為到達），兩種都能過，但用 inf 的語意比較嚴謹。

自底向上

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        costs = [0] * (len(cost) + 1)
        costs[0] = cost[0]
        costs[1] = cost[1]
        cost.append(0)
        
        i = 2
        while i < len(costs):
            costs[i] = cost[i] + min(costs[i-1], costs[i-2])
            i += 1

        return costs[-1]

這版的 costs[i] 是「走到第 i 階並付完它的錢」，方向和自頂向下相反。cost.append(0) 是為了讓終點（索引 n）有一個「花費 0」的格子，這樣最後一格就能套用同一條轉移式，回傳 costs[-1] 即可。

它會改到輸入：cost.append(0) 讓呼叫端的陣列多了一個元素（[10,15,20] 跑完會變成 [10,15,20,0]）。LeetCode 不會因此判錯，但在真實程式碼裡這是要避免的副作用，正式一點應該複製一份或另外處理終點。

空間可以降到 $O (1)$ ，因為只用到前兩格：

        prev, curr = 0, 0
        for i in range(2, len(cost) + 1):
            prev, curr = curr, min(curr + cost[i-1], prev + cost[i-2])
        return curr

補充

和 70. Climbing Stairs 的關係：70 問「有幾種走法」（把兩條路徑相加），這題問「最少花多少」（把兩條路徑取小）。同一個遞推骨架，換一個聚合函式就換一題 —— 這是 DP 題最常見的變形方式，值得記住這組對照。

同一類的一維遞推：198. House Robber、91. Decode Ways（遞推加上條件判斷）。整理見 Dynamic Programming 模板。

複雜度

自頂向下（@cache）

時間 $O (n)$ — 每個 i 只算一次
空間 $O (n)$ — cache 加上遞迴堆疊

自底向上

時間 $O (n)$ — 一個迴圈
空間 $O (n)$ — costs 陣列；用滾動變數可降到 $O (1)$

其中 n 是樓梯的階數。