---
title: "518. Coin Change 2"
url: "https://laigary.com/interview/coding/518-coin-change-2"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-08-01"
tags: ["Dynamic Programming"]
---

# 518. Coin Change 2

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

給定硬幣面額和目標金額，問湊出目標金額總共有幾種**組合** —— 只看每種面額各用了幾枚，不看順序。

## 思路

這個題目是 [322 Coin Change](/interview/coding/322-coin-change) 的進階題目，該題是個動態規劃的問題，目標是要找到使用最少的硬幣組合，而這道題目並不要求找到最少的硬幣，而是要找出總共有幾種組合，這個題目就變成了一個窮舉的題目。

但是這個裡面的窮舉，只在乎某個面額的硬幣，總共使用了幾枚，並不在乎到底是用什麼數量排出的，例如當硬幣的面額有 `[1, 2]` 兩種，目標是要找到 `5` 元的硬幣，`[1, 2, 2]`, `[2, 2, 1]` 這兩種組合都是使用一枚一元、兩枚兩元，並不重複計算。

這也就是這個題目比較困難的地方。

1.  既然是要窮舉，Backtracking 應該是最適合的，但是 Backtracking 會把各種排列組合都計算進去，當然可以透過一些方法在窮舉時排除掉重複的情況，但是多會增加時間複雜度。
2.  雖然是窮舉，但是我們可以把以上出現重複的組合，視為重複的子問題，也就是說如果我們知道怎麼樣的情況會是重複的子問題，就可以把窮舉改寫成動態規劃的表達式。

### 觀察窮舉的過程

這時候可以先觀察這個題目窮舉的過程

1.  在選硬幣的過程中，可以把能選用的硬幣依照幣值大小排列好。
2.  如果從幣值最小的先選，通常可以選出最多枚，接著拿出部分最小值的硬幣，以面額次小的硬幣取代掉，不斷的重複這個過程，就可以知道最後有哪些組合了。
3.  如果從幣值最大的先選，通常會選出最少枚硬幣，接著每次拿出面額最大的硬幣，用面額次大的硬幣取代，不斷的重複這個過程，就可以知道最後有哪些組合了。

從上述的過程中，不管是從面額小的開始去選擇，還是從面額大的去選擇，基本上都可以找出答案，其中最重要的一個點就是，從當前的面額來看時，要往一個恆定的方向去找，那就是只能朝面額更大的方向去找，或是朝面額更小的地方去找。

這樣的方式可以很有系統性地去找出所有的組合，不過這裡有一個但書，那就是題目並沒有告訴我們說所有的硬幣是依序排列的，所以透過上述的觀察，我們需要多做一個排序來完成我們的演算法。

### 排序有必要嗎

這個題目其實存在著不需要先排序過的答案，但是我覺得面試時有著上述的觀察其實並沒有什麼不對，沒有寫過題目的人本來就會需要先透過觀察來完成題目的需求。

只是這裡存在著一個討論，那就是排序到底是有沒有必要的？例如：題目給定了 `[2, 1, 5]` ，那是不是可以先把 `2` 給利用完了後，再開始看 `1` 呢？其實仔細想一下，這完全是沒有問題的，因為其實這個題目的精髓是慢慢地取代掉面額，因此只要嚴格地從當前的位置選出要多少個，並且剩下的面額都是從右方的面額選取，那就依然可以窮舉出所有的選擇。排序其實只是方便人類去思考，對於電腦來說，這樣的記憶量是很輕鬆的。

這樣其實我們就可以完成動態轉移方程了。

## 解題方向

### 自頂向下

`dfs(remaining, index)` 的定義是：**只准用 `coins[index:]` 這些面額，湊出 `remaining` 有幾種組合**。設總共有 `n` 種面額：

$$
f(remaining,\ index) = \sum_{i=index}^{n-1} f(remaining - coins[i],\ i)
$$

邊界有兩條：`f(0, index) = 1`，湊剛好就是一種湊法；`remaining < 0` 時回傳 0，代表這條路走不通。

式子裡有兩個地方是這題的關鍵，剛好對應上面觀察到的兩件事：

-   `i` 從 `index` 開始而不是從 0 開始 —— 這就是「只能朝一個恆定的方向去找」，不回頭就不會把 `1+2+2` 和 `2+2+1` 數成兩種
-   遞迴傳下去的是 `i` 而不是 `i + 1` —— 同一種面額可以再拿一枚

```python
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        @cache
        def dfs(remaining, index):
            if remaining < 0:
                return 0
            if remaining == 0:
                return 1

            count = 0
            for i in range(index, len(coins)):
                coin = coins[i]
                count += dfs(remaining - coin, i)
            return count
        
        return dfs(amount, 0)
```

### 自底向上

`dp[i]` 的定義是：**湊出金額 `i` 有幾種組合**。

不過一維的樣子是壓縮過的，先把二維寫出來比較好懂。令 `dp[j][i]` 是「只用前 `j` 種硬幣、湊出金額 `i` 的組合數」，第 `j` 種硬幣的面額寫成 $coin_j$：

$$
dp[j][i] = dp[j-1][i] + dp[j][i - coin_j]
$$

-   `dp[j-1][i]` —— **不用**第 `j` 種硬幣，那答案就跟只有前 `j-1` 種時一樣
-   `dp[j][i - coin_j]` —— **用掉一枚**第 `j` 種硬幣。注意這裡還是 `j` 不是 `j-1`，因為同一種硬幣可以再拿

邊界是 `dp[j][0] = 1`：湊出 0 元有一種方法，就是什麼都不拿。**這是整張表唯一的 1，其他所有數字都是從它一路加回來的。**

程式碼裡的一維 `dp` 就是把 `j` 這個維度滾掉：外層 `for coin in coins` 走的就是 `j`，`dp` 每跑完一輪就地變成「多考慮了這一種硬幣」的版本。所以 `dp[i] += dp[i - coin]` 讀起來就是上面那條式子 —— 等號左邊被加的舊值是 `dp[j-1][i]`，加上去的是 `dp[j][i - coin]`。

**兩層迴圈的順序不能對調。** 外層硬幣、內層金額算的是**組合**；對調成外層金額、內層硬幣，算出來的會是**排列**：

| amount / coins | 這裡的寫法 | 對調之後 |
|---|---|---|
| 5 / `[1, 2, 5]` | 4 | 9 |
| 10 / `[2, 3, 5]` | 4 | 14 |
| 8 / `[1, 2, 3]` | 10 | 81 |

對調之後那一欄正好是「377. Combination Sum IV」要的答案，因為外層變成金額之後，每個金額都會把所有面額再問一次，`1+2+2` 和 `2+2+1` 就被分開數了。這也就是思路裡說的「要往一個恆定的方向去找」—— 那個方向在這裡就是外層迴圈。

**內層必須從小到大。** `dp[i - coin]` 在同一輪裡已經被更新過，代表「這種硬幣可以再拿一枚」。如果內層改成從大到小，`dp[i - coin]` 讀到的還是上一輪的值，每種硬幣就只能用一次 —— 那是 0/1 背包，也就是 [416. Partition Equal Subset Sum](/interview/coding/416-partition-equal-subset-sum) 的形狀。上面那三筆測資倒著跑會變成 1、1、0。

至於**外層硬幣本身的先後順序，一樣是無所謂的** —— 和上面「排序有必要嗎」那段的結論一致，`coins` 有沒有排序、怎麼排，答案都相同。

整理見 [Dynamic Programming 模板](/interview/coding/dynamic-programming-template)裡「兩層迴圈的順序決定題型」那段。

```python
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]
        return dp[amount]

```

## 複雜度

設 `amount` 是目標金額、`n` 是硬幣的種類數。

**自頂向下**
- 時間 $O(amount \times n^2)$ — 狀態是（剩餘金額, 從哪個面額開始選），共 $O(amount \times n)$ 個，而每個狀態裡的迴圈最多跑 `n` 次
- 空間 $O(amount \times n)$ — cache 的大小；另外遞迴深度是 $O(amount)$，一路都選最小面額的時候最深

**自底向上**
- 時間 $O(amount \times n)$ — 就是兩層迴圈，外層 `n` 種硬幣、內層 `amount` 格
- 空間 $O(amount)$ — 只有一維的 `dp`

兩者差了一個 `n`，差別在於自頂向下每個狀態都要重跑一次「從 `index` 開始的每種面額」，而自底向上把「這一種面額」提到外層迴圈，一種只處理一次。