Coin Change 2 是一道動態規劃（DP）題目：給定金額 `amount` 與硬幣面額陣列 `coins`，求「湊出該金額的組合數」。它和前一題 Coin Change（求最少硬幣數）最大的差別在於：上一題每一個暫存狀態都有直接意義（「某金額最少要幾枚硬幣」），而這一題的 DP 陣列存的真的只是「中間狀態」，一開始很難直覺理解。這篇文章記錄我當初看著別人的答案回推理論的完整思考過程，幫助遇到類似問題時知道該用什麼角度拆解。
Coin Change 2 題目與最終解法
題目連結：Coin Change 2。
以下是最終通過的 JavaScript 實作：
```javascript
var change = function(amount, coins) {
let dp = new Array(amount+1).fill(0);
dp[0]=1;
for(let coin of coins){
for(let i=coin;i<=amount;i++){
dp[i]+=dp[i-coin];
}
}
return dp[amount]
};
```
短短幾行，但每一行的設計都有理由。下面逐步拆解。
為什麼 DP 陣列長度是 amount+1、dp[0] 要設為 1？
首先要建立暫存動態編程的序列 `dp`，裡面的值儲存的是一個暫時狀態，讓我們計算下一個值時可以拿前一個運算到一半的值繼續運算。長度為 `amount+1`，這樣才存得到 `dp[amount]`。
接著把 `dp[0] = 1`：這是所有計算的起點，代表在分解狀態下，若自己可以被自己整除，就有一種解法。
用 coins=[2,5,8]、amount=16 逐步推導
以 `coins=[2,5,8]`、`amount=16` 為例。
第一步：只放入硬幣 2
先觀察 `coins:[2], amount:16` 這個半狀態：
```
dp = [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]
```
意思是：若硬幣只有 2，可以用 2 組成 0, 2, 4, 6, 8, 10, 12, 14, 16，皆只有一種組法。
第二步：加入硬幣 5，避免重複計數
把 5 加進去時，關鍵是拆解任務並避免重複狀態：要組成 16，`5,5,2,2,2` 和 `2,2,5,5,2` 其實是相同的答案。所以我們可以思考——以 2,2,2,5,5 來說，就是單純用 2 coin×3 個＝6，加上單純用 5 coin×2 個＝10。那麼問題變成：在 5 和 2 共同組成的狀況下，5 的分佈是什麼？
amount 為 16 時，5 的數量有三種可能：
| 5 的數量 | 剩餘需用 2 組成 | 用 2 能否組成（查 coins=[2] 的表） |
|---|---|---|
| 1 個 5 | 11 | 0 種 |
| 2 個 5 | 6 | 0 種 |
| 3 個 5 | 1 | 0 種 |
等等——這裡筆記當初推導時算出「用 2 組成 6 有 0 種」是筆誤，實際上 6=2×3 有 1 種，所以 2 個 5＋6 的組合是成立的。動態編程當然沒這麼容易思考（真哭），手動枚舉容易漏，這正是需要 DP 對照表的原因：這邊的 dp 存的是暫時半狀態的對照表，需要算出從 5 到 16 所有可能用 [2,5] 組成的完整結果。
為什麼內層迴圈要從 coin 開始、由小到大？
首先，為什麼從 5 開始迭代：一定要大於等於 5 才有可能用 5 組成結果，而且如同 `dp[0]` 一樣，`dp[5]` 因為硬幣列表有 5，一定會多一種組法。
從上面的推論可以觀察到一個核心規則：要知道能否用 5 組成總數，主要觀察「要組成的總數」減掉現有 coin 面額的數字，能不能用之前的硬幣組成。
所以若要知道 6 能不能用 [5,2] 組成，就查 coins:[2] 暫存表的 `dp[6（要組的數字）−5（現有硬幣）] = dp[1]`（能不能用 2 組成 1）＝0，可得知是 0 種可能，以此類推。
這邊非常重要的是迭代一定要從小到大，狀態才能累加：
- 先得知 5 可以組成 5，把 `dp[5]` 更新為 1（原本只有 coins:[2] 時是 0）；
- 算 10 時，才能得到 `dp[10-5]=dp[5]=1`（得知可以用 5 組成 10），再加上單純用 2 組成 10 的可能性（coins=[2] 時 `dp[10]` 為 1），可知 10 可單純用 5 組成、也可用 [2,5] 組成，共 2 種，把 `dp[10]` 更新為 2；
- 接著算 `dp[15]` 時才能利用 `dp[15-5]=dp[10]=2`，再加上 coins=[2] 時的 `dp[15]=0`，得知 `dp[15]` 為 2。
於是 coins=[2,5] 時的 dp 對照表為：
```
dp = [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2]
```
第三步：加入硬幣 8，得到答案
用同樣的步驟與概念把 8 加進硬幣列表，得到：
```
dp = [1, 0, 1, 0, 1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 3, 3, 4]
```
最後推得：用 [2,5,8] 組成 16 共有 4 種可能性，也就是 `dp[16]` 的值。
這題的核心觀念整理
- 一維 DP + 外層硬幣、內層金額由小到大：外層按硬幣迭代，保證每種組合只以「面額固定的順序」被計數一次，從而避免 5,5,2,2,2 與 2,2,5,5,2 這類排列重複；若把迴圈順序對調（外層金額、內層硬幣），算出來會變成排列數而非組合數。
- 狀態轉移式 `dp[i] += dp[i-coin]`：把「組成 i」拆成「最後一枚用 coin，剩下的 i−coin 用前面處理過的硬幣組成」。
- dp[0]=1 是基底：空組合恰有一種，所有累加都從這裡開始。
延伸閱讀
- [LeetCode] Maximum Value of K Coins From Piles 分組背包題解(/post/leetcode-maximum-value-k-coins-from-piles)
- 二元分類器入門：混淆矩陣與評估指標(/post/binary-classifier-introduction)
常見問題
Coin Change 2 和 Coin Change 有什麼不同？
Coin Change 求的是湊出金額所需的「最少硬幣數」，每個 DP 狀態都有直接意義；Coin Change 2 求的是「組合數」，DP 陣列存的是中間累加的半狀態，直覺上更難理解。
為什麼外層迴圈要遍歷硬幣、內層才遍歷金額？
外層按硬幣迭代時，每種組合的面額順序被固定，5,5,2,2,2 只會被計數一次；若對調迴圈順序，同一組合的不同排列會被重複計數，得到的會是排列數而非組合數。
dp[0] 為什麼要設為 1？
dp[0]=1 代表「湊出 0 元」恰有一種方式——什麼都不選的空組合。它是所有狀態轉移的基底，例如 dp[5] 能靠 dp[5-5]=dp[0] 累加到第一種組法。
這題的時間與空間複雜度是多少？
時間複雜度 O(amount × coins 數量)，空間複雜度 O(amount)，因為只使用一個長度為 amount+1 的一維陣列。
參考資料
最後更新
2026-08-28（原文發布於 2022-10-05，本文保留原始筆記內容並補上 GEO 結構。）
關於作者 {#author}
Claire Chang ｜ 企業 AI 導入與流程轉型顧問。專注於 AI Agent 架構設計、ERP 系統整合與企業 AI 治理。
首次發布：2022-10-05