---
title: "322. Coin Change"
url: "https://laigary.com/interview/coding/322-coin-change"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-29"
tags: ["Dynamic Programming", "Array", "Classic"]
---

# 322. Coin Change

[322\. Coin Change](https://leetcode.com/problems/coin-change/)

給定總金額 `amount` 和硬幣面額 `coins`（每種面額數量無限），問湊出 `amount` 最少要幾枚硬幣，湊不出來就回傳 -1。

例如金額 11、面額 `[1, 2, 5]`，最少是兩枚 5 加一枚 1，答案 3。如果金額是 3 而面額只有 `[2]`，湊不出來，回傳 -1。

## 思路

### 先說為什麼貪心是錯的

生活經驗會說「盡可能先用最大面額，不夠再往次大的找」。這個直覺很強，但這題不成立，原因有三個層次：

1. 題目**沒有保證** `coins` 是排好序的
2. 先用大面額可能導致剩下的金額根本湊不出來，還要能退回去重試
3. 就算處理掉前兩點，貪心**本身就是錯的**

第三點才是關鍵，一個反例就夠：

```text
coins = [1, 3, 4], amount = 6

貪心：4 → 剩 2 → 1 → 1      3 枚
最佳：3 + 3                 2 枚
```

貪心在第一步拿走 4，而 4 這個選擇讓剩下的 2 只能用兩個 1 湊。根本原因是**面額之間可以互相取代**：4 和 3+1 都是 4 塊錢，但它們對「剩下要湊多少」的影響完全不同，而你在拿的當下無從判斷。

只要一題出現「這一步選什麼，會改變剩下能選什麼的組合」，貪心就不成立 —— 判斷方式見 [Greedy 模板](/interview/coding/greedy-template)。這題也正是那篇拿來當反例的題目。

### 貪心不行，那就窮舉

既然沒辦法在當下判斷，那就每種面額都試一次，讓電腦去窮舉。遞迴式非常直白：

$$
f(remaining) = 1 + \min_{coin \in coins} f(remaining - coin)
$$

「湊出 `remaining` 最少要幾枚」＝「先拿一枚（不管拿哪種），再湊剩下的」，取所有選法裡最小的那個。

邊界條件有三種：

- `remaining < 0` —— 拿爆了，這條路不通，回 -1
- `remaining == 0` —— 剛好湊完，回 0
- 其他 —— 繼續遞迴

## 解題方向

### 純遞迴（會超時）

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def helper(remaining):
            if remaining < 0:
                return -1
            elif remaining == 0:
                return 0
            else:
                # f(remaining) = 1 + min(f(remaining-coin[1]), ..., f(remaining-coin[n]))
                min_cost = float('inf')
                for coin in coins:
                    res = helper(remaining - coin)
                    if res != -1:
                        min_cost = min(min_cost, res + 1)
                if min_cost != float('inf'):
                    return min_cost
                else:
                    return -1
        return helper(amount)
```

`float('inf')` 當[哨兵](/interview/coding/python-tips-for-interview)，代表「目前還沒找到任何可行解」。最後如果它沒被更新過，就代表所有面額都走不通，回 -1。

這份程式碼是正確的，但會超時 —— 因為同一個 `remaining` 會被重複計算很多次。以 `coins = [1, 2, 5]` 為例，`f(9)` 可以從 `11 - 2` 到達，也可以從 `11 - 1 - 1` 到達，兩條路各算一遍。

### Top-Down：加上 `@cache`

能記憶化的前提是：**`f(remaining)` 只跟 `remaining` 有關，跟「你是怎麼走到這個 remaining 的」完全無關。** 確認了這件事，加一行裝飾器就好：

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        @cache
        def helper(remaining):
            if remaining < 0:
                return -1
            if remaining == 0:
                return 0
            min_cost = float('inf')
            for coin in coins:
                res = helper(remaining - coin)
                if res != -1:
                    min_cost = min(min_cost, res + 1)
            return min_cost if min_cost != float('inf') else -1

        return helper(amount)
```

`@cache` 做的事就是「查表 → 沒有就算 → 存回去」，跟手寫一個字典一模一樣。但它有一個手寫版容易忘記的好處：**`-1` 也會被快取**。手寫的時候如果只在找到答案時才存進字典，那些湊不出來的分支會被反覆重算，記憶化等於白做。

`@cache` 來自 `functools`，用法見 [Python 面試技巧](/interview/coding/python-tips-for-interview)。

### Bottom-Up

Top-down 是「從 `amount` 往下拆」，bottom-up 反過來 —— **從 0 開始，一路把每個金額的答案都填出來**，填到 `amount` 就結束。

`dp[i]` 的定義是：湊出金額 `i` 最少要幾枚硬幣。

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 如果沒有最佳解，則該解為無限大
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(len(dp)):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], 1 + dp[i-coin])

        return -1 if dp[amount] == float('inf') else dp[amount]
```

`dp[0] = 0` 是唯一的起點：湊出 0 塊需要 0 枚。之後每個 `dp[i]` 都只依賴比它小的格子，所以由小往大填一定填得完。

`float('inf')` 在這裡同時扮演兩個角色：初始值（還沒算出來）和「湊不出來」的標記。因為 `1 + inf` 還是 `inf`，湊不出來的狀態會自動往後傳播，不需要特別處理。

**外層跑金額、內層跑硬幣 —— 這題兩層迴圈交換順序不影響答案**，因為求的是最少個數。但在 [518. Coin Change 2](/interview/coding/518-coin-change-2) 求「有幾種湊法」時，順序交換就會把答案從「組合數」變成「排列數」。那是背包題最經典的坑。

## 補充

**背包三形態**（見[總索引](/interview/coding/coding-interview-preparation)）：

| 題目 | 背包類型 | 問什麼 |
|---|---|---|
| 322 | 完全背包（每種無限用） | 最少幾個 |
| [518. Coin Change 2](/interview/coding/518-coin-change-2) | 完全背包 | 有幾種湊法 |
| [416. Partition Equal Subset Sum](/interview/coding/416-partition-equal-subset-sum) | 0/1 背包（每個用一次） | 可不可行 |

三題的狀態轉移幾乎一樣，差別全在「迴圈順序」和「要 min、要加總、還是要 or」。放在一起寫最能看出差異。

**貪心什麼時候才對？** 台幣、美元這種面額（1、5、10、50、100…）貪心確實是對的，這類幣制有個名字叫 canonical coin system。但那是**幣制的性質**，不是問題的性質 —— LeetCode 會給你任意面額，所以不能靠它。

## 複雜度

以下都用 $A$ 表示 `amount`、$k$ 表示面額的種類數。

- **純遞迴** — 時間 $O(k^A)$，每層展開 $k$ 個分支、深度最多 $A$；空間 $O(A)$ 是遞迴深度
- **Top-down（`@cache`）** — 時間 $O(A \times k)$，狀態只有 $A + 1$ 個，每個狀態試 $k$ 種面額；空間 $O(A)$ 是快取加上遞迴堆疊
- **Bottom-up** — 時間 $O(A \times k)$ 一樣；空間 $O(A)$ 只有 `dp` 陣列，沒有遞迴堆疊

兩種 DP 寫法複雜度相同，bottom-up 的常數比較小而且不會有遞迴深度的問題。