---
title: "746. Min Cost Climbing Stairs"
url: "https://laigary.com/interview/coding/746-min-cost-climbing-stairs"
type: "note"
section: "coding"
date: "2024-01-05"
updated: "2026-07-28"
tags: ["Dynamic Programming"]
---

# 746. Min Cost Climbing Stairs

[746\. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)

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

## 思路

這題是 [70. Climbing Stairs](/interview/coding/70-climbing-stairs) 加上花費，但有兩個地方特別容易搞錯，都跟**邊界的定義**有關：

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

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

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

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

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

$$
dp(i) = cost[i] + \min\bigl(dp(i+1),\; dp(i+2)\bigr)
$$

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

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

## 解題方向

### 自頂向下

```python
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` 的語意比較嚴謹。

### 自底向上

```python
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)$**，因為只用到前兩格：

```python
        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](/interview/coding/70-climbing-stairs) 的關係**：70 問「有幾種走法」（把兩條路徑**相加**），這題問「最少花多少」（把兩條路徑**取小**）。**同一個遞推骨架，換一個聚合函式就換一題** —— 這是 DP 題最常見的變形方式，值得記住這組對照。

**同一類的一維遞推**：[198. House Robber](/interview/coding/198-house-robber)、[91. Decode Ways](/interview/coding/91-decode-ways)（遞推加上條件判斷）。整理見 [Dynamic Programming 模板](/interview/coding/dynamic-programming-template)。

## 複雜度

**自頂向下（`@cache`）**
- 時間 $O(n)$ — 每個 `i` 只算一次
- 空間 $O(n)$ — cache 加上遞迴堆疊

**自底向上**
- 時間 $O(n)$ — 一個迴圈
- 空間 $O(n)$ — `costs` 陣列；用滾動變數可降到 $O(1)$

其中 `n` 是樓梯的階數。