面向大象程式設計
換硬币（Coin Change）問題是一道經典的動态規劃入門題，但是你可能不太知道，LeetCode 上的換硬币問題其實是一個系列，共三道題目：
- LeetCode 322. Coin Change（Medium）
- LeetCode 377. Combination Sum IV（Medium）
- LeetCode 518. Coin Change 2（Medium）
其中，377 題雖然不叫 Coin Change，但是本質上和換硬币問題是一樣的。
這一系列是比較考驗技巧的三道題目，難度層層遞進。第一道題是大家都熟悉的動态規劃入門題；第二道題變為求方案數，需要我們不重複不遺漏；第三道題更有難度，需要擴充為二維動态規劃，才能準确求出方案數量。
沒有做過這個系列三道題的同學，不妨跟着本文看看三道題目的解法，了解其中的思路和技巧。下面我們一道一道地進行分析。
(一) 第 322 題：求最小硬币數
LeetCode 322. Coin Change（Medium）
給定不同面額的硬币 和金額 coins
amount
，計算湊成總金額所需的最少的硬币個數。如果沒有任何一種方案能組成該金額，傳回 -1。每種硬币的數量是無限的。
示例：
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
這第一道題目大家應該都做過，網上的各種解析也很泛濫。這裡我們還是套用動态規劃的解題四步驟來求解。
第一步，定義子問題。
我們設硬币面值的集合為
。子問題
可以定義為：「湊出金額
的最小硬币數」。那麼原問題就是求
。
第二步，寫出子問題的遞推關系。
求「湊出金額
的最小硬币數」，我們可以嘗試不同的硬币。如果使用了金額為
的硬币，問題就變成了「湊出金額
這樣我們就可以寫出子問題的遞推關系：
當然，不要忘記子問題的 base case：
它的含義是，當
amount
為 0 時，不需要任何硬币就已經湊出了目标金額。
第三步，确定 DP 數組的計算順序。
确定 DP 數組計算順序的重點是看子問題的依賴關系。我們以
為例，即有 1 元、2 元、5 元的硬币。這樣
依賴于
、
、
，全部在
DP 數組中的依賴關系
既然 DP 數組中的依賴關系都是向右指的，那麼 DP 數組的計算順序就是從左到右。
處理 DP 數組中的無效元素。
至此，我們離寫出題解代碼已經很接近了，但還要處理一個程式設計上的細節：DP 數組中的無效元素。
可能存在一些金額是硬币湊不出來的。例如隻有 2 元、5 元的硬币時，就湊不出 1 元、3 元的金額。這樣
、
為了計算友善，我們可以把無效的子問題用
（正無窮大）表示。這是因為子問題的遞推關系求的是最小值
，正無窮大的值顯然不會成為最小值。這樣無效元素也能參與計算了。
在程式設計表示中，我們發現 DP 數組中的值最大也隻能是
amount
（隻有 1 元硬币的情況，硬币數量等于金額數），我們可以用
amount + 1
表示
。DP 數組中的值隻要大于
amount
，就認為是無效元素。
這樣，我們就可以寫出最終的題解代碼：
public int coinChange(int[] coins, int amount) {
// 子問題：
// f(k) = 湊出金額 k 的最小硬币數
// f(k) = min{ 1 + f(k - c) }
// f(0) = 0
int[] dp = new int[amount+1];
Arrays.fill(dp, amount + 1); // DP 數組初始化為正無窮大
dp[0] = 0;
for (int k = 1; k <= amount; k++) {
for (int c : coins) {
if (k >= c) {
dp[k] = Math.min(dp[k], 1 + dp[k-c]);
}
}
}
// 如果 dp[amount] > amount，認為是無效元素。
if (dp[amount] > amount) {
return -1;
} else {
return dp[amount];
}
} 這道題進行空間優化很麻煩，是以我們忽略第四步空間優化的步驟。
(二) 第 377 題：求方案數
LeetCode 377 - Combination Sum IV（Medium）
給定一個由正整數組成且不存在重複數字的數組 ，找出和為給定目标正整數 nums
target
的組合的個數。順序不同的序列視作不同的組合。
示例：
，nums = [1, 2, 3]
target = 4
。所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
别看這道題表面上看起來跟換硬币沒啥關系，但如果你把數字
nums
變成硬币
coins
，把
target
變成
amount
，它就成了一道如假包換的換硬币問題：
給定不同面額的硬币 和金額 coins
，計算湊出該金額的方案的個數。順序不同的序列視作不同的方案。amount
這道題和上一題的不同在于，不是求「最小的硬币數量」，而是求「方案的個數」。這樣問題的難度又上了一個台階。
求「方案數」的難度在于要做到不重複、不遺漏。如果是求「最小值」，其實子問題之間可以有重複，也能求出正确的最小值；但是求「方案數」時，子問題之間的重複會導緻方案數不正确。這一點一定要特别注意。
第一步，定義子問題。
我們還是設硬币面值的集合為
。子問題
可以定義為：「湊出金額
的方案的個數」。那麼原問題就是求
。
第二步，寫出子問題的遞推關系。
我們可以把湊硬币的方案看成硬币的排列。對于
即「湊出金額
的方案數」，我們考慮第一個硬币選哪個。以
為例，第一個硬币放 1、2 或 5 顯然都是不同的方案。如果第一個硬币放的是 1，剩下的金額
的方案個數是
。這樣我們可以得出：
把這個公式推廣到一般的硬币面值集合
，就得到了子問題的遞推關系：
同樣的，不要忘記子問題的 base case：
它的含義是「湊出金額 0 的方案數為 1」。這是求「方案數」時一個常見的技巧。所有的
最後都要轉化為
第三步，确定 DP 數組的計算順序。
這道題的 DP 數組及其計算順序和上一題是一樣的，這裡不再贅述。
DP 數組中的依賴關系
DP 數組中不存在什麼無效元素。湊不出的金額我們可以用
這樣我們就可以寫出題解代碼了。這一題的主要難度在于遞推關系的細節，最終寫出的題解代碼還是挺簡單的：
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1]; // 預設初始化為 0
dp[0] = 1; // 注意 base case
for (int k = 1; k <= target; k++) {
for (int n : nums) {
if (k >= n) {
dp[k] += dp[k-n];
}
}
}
return dp[target];
} (三) 第 518 題：不重複的方案數
LeetCode 518. Coin Change 2（Medium）
給定不同面額的硬币 和金額 coins
amount
。寫出函數來計算可以湊成該金額的硬币組合數。假設每一種面額的硬币有無限個。
示例：
輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
這道題和上一題的差別在于，順序不同的序列視為同一種方案。這一個小小的改動，讓題目的難度瞬間上升。我們在上一題中寫出的子問題遞推關系不再适用了。
例如要湊出金額 5，本題中将「2+2+1」和「1+2+2」視為同一種方案。我們不能再像上一題中那樣，先考慮第一個硬币是 1、2、5，再看後面的方案了。
那麼，如何去除像「2+2+1」和「1+2+2」這樣重複了的序列呢？其實，這非常像「排列」跟「組合」的關系：上一題中将順序不同的序列視為不同的方案，類似「排列」問題；這一題中将順序不同的序列視為相同的方案，類似「組合」問題。
我們已經在前面的文章中讨論過排列問題與組合問題的關系：
LeetCode 例題精講 | 08 排列組合問題：回溯法的候選集合
要将順序不同的排列視為同一個組合，隻需要考慮所有有序的排列，丢棄其他的排列。
對于硬币問題，就是限制硬币選擇的次序，先選面額大的硬币，再選面額小的硬币。也就是說，我們隻允許「2+2+1」這樣先大後小的硬币序列出現，不允許「1+2+2」這樣的硬币序列。
如何限制硬币選擇的次序呢？答案是動态規劃增加一個次元，用參數
第一步，定義子問題。
設硬币面值的集合為
。子問題
表示用前
個硬币（即
）湊出金額
在一開始，
，即可以選擇全部的
個硬币。假如在目前一步選擇了面額第二大的硬币
，那麼接下來
變為
，限制後面隻能選比
第二步，寫出子問題的遞推關系。
子問題的遞推關系是這樣的：
這個遞推關系是怎麼來的呢？考慮子問題
，用硬币
湊出金額
第一種選擇：拿一個面額最大的硬币
，因為一種硬币可以重複拿多次，後面
還都可以随便選，方案數為
。
第二種選擇：決定不再拿面額最大的硬币
，後面隻能選
，方案數為
。
你可以會問，為什麼沒有
？其實我們的公式已經把這種情況包括在裡面了。
這樣，原問題就是
，即用全部的
個硬币湊出金額
amount
的方案數。
另外别忘了子問題的 base case。這道題的 base case 同樣比較複雜：
-
當
時，
。即「湊出金額 0 的方案數為 1」，與上一題一樣的技巧。
-
當
時，
。硬币用完後，湊不出任何金額。
第三步，确定 DP 數組的計算順序。
我們發現，這一題增加了一個次元，變成了二維動态規劃問題。這樣我們就更需要确定 DP 數組的計算順序了。接下來為了讨論友善，我們設硬币的種類為
，要湊出的金額（
amount
）為
。
首先，DP 數組的有效範圍是
。在 DP 數組中，base case 位于 DP 數組的最左側一列和最上方一行，而原問題則位于 DP 數組的右下角，如下圖所示。
DP 數組的特殊值
這張圖中特意把 DP 數組畫成一個很扁的長方形，是因為一般情況
要比
大很多。
表示要湊出的金額
amount
，而
子問題的依賴關系在 DP 數組中是這樣子的：
DP 數組中的依賴關系
可以看到，子問題的依賴方向是向右、向下的。那麼我們應該從左到右、從上到下周遊 DP 數組，計算其中的元素。
最終，我們可以寫出這樣的題解代碼：
public int change(int amount, int[] coins) {
int m = coins.length;
int[][] dp = new int[m+1][amount+1];
for (int i = 0; i <= m; i++) {
for (int k = 0; k <= amount; k++) {
if (k == 0) {
dp[i][k] = 1; // base case
} else if (i == 0) {
dp[i][k] = 0; // base case
} else {
dp[i][k] = dp[i-1][k];
if (k >= coins[i-1]) {
dp[i][k] += dp[i][k-coins[i-1]];
}
}
}
}
return dp[m][amount];
} 眼尖的同學可能已經看出來，這其實是一道背包問題。那麼，這道題可以用背包問題的通用空間優化方法進行優化，把二維的 DP 數組變成一維的。不過考慮到這個空間優化比較難，大家也都不怎麼熟悉背包問題，這裡我們省去了空間優化的步驟。後面會有專門的背包問題文章講解相關的技巧。
總結
比較換硬币系列三道問題，我們發現它們各有不同，總體難度循序漸進，其實非常适合作為一個系列的練習題。
| 題目 | 計算目标 | 次元 |
| 322. Coin Change | 最小硬币數量 | 一維 |
| 377. Combination Sum IV | 方案數 | 一維 |
| 518. Coin Change 2 | 方案數 | 二維 |
如果三道題中有幾道你還沒有做過，強烈建議你在看完本文後按照這個順序依次做一遍題目，可以加深對這一系列題目的了解。
歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下