重磅乾貨，第一時間送達
轉自面向大象編程
換硬幣（Coin Change）問題是一道經典的動態規劃入門題，但是你可能不太知道，LeetCode 上的換硬幣問題其實是一個系列，共三道題目：
其中，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 數組計算順序的重點是看子問題的依賴關係。我們以
DP 數組中的依賴關係既然 DP 數組中的依賴關係都是向右指的，那麼 DP 數組的計算順序就是從左到右。
處理 DP 數組中的無效元素。
至此，我們離寫出題解代碼已經很接近了，但還要處理一個編程上的細節：DP 數組中的無效元素。
可能存在一些金額是硬幣湊不出來的。例如只有 2 元、5 元的硬幣時，就湊不出 1 元、3 元的金額。這樣
為了計算方便，我們可以把無效的子問題用
在編程表示中，我們發現 DP 數組中的值最大也只能是 amount（只有 1 元硬幣的情況，硬幣數量等於金額數），我們可以用 amount + 1 表示
這樣，我們就可以寫出最終的題解代碼：
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，計算湊出該金額的方案的個數。順序不同的序列視作不同的方案。
這道題和上一題的不同在於，不是求「最小的硬幣數量」，而是求「方案的個數」。這樣問題的難度又上了一個臺階。
求「方案數」的難度在於要做到不重複、不遺漏。如果是求「最小值」，其實子問題之間可以有重複，也能求出正確的最小值；但是求「方案數」時，子問題之間的重複會導致方案數不正確。這一點一定要特別注意。
第一步，定義子問題。
我們還是設硬幣面值的集合為
第二步，寫出子問題的遞推關係。
我們可以把湊硬幣的方案看成硬幣的排列。對於
把這個公式推廣到一般的硬幣面值集合
同樣的，不要忘記子問題的 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」這樣的硬幣序列。
如何限制硬幣選擇的次序呢？答案是動態規劃增加一個維度，用參數
第一步，定義子問題。
設硬幣面值的集合為
在一開始，
第二步，寫出子問題的遞推關係。
子問題的遞推關係是這樣的：
這個遞推關係是怎麼來的呢？考慮子問題
第一種選擇：拿一個面額最大的硬幣
第二種選擇：決定不再拿面額最大的硬幣
你可以會問，為什麼沒有
這樣，原問題就是
另外別忘了子問題的 base case。這道題的 base case 同樣比較複雜：
當