經典動態規劃：完全背包問題
讀完本文，你可以去力扣拿下如下題目：
———–
零錢兌換 2 是另一種典型背包問題的變體，我們前文已經講了 經典動態規劃：0-1 背包問題。
希望你已經看過前兩篇文章，看過了動態規劃和背包問題的套路，這篇繼續按照背包問題的套路，列舉一個背包問題的變形。
本文聊的是 LeetCode 第 518 題 Coin Change 2，題目如下：
int change(int amount, int[] coins);
PS：至於 Coin Change 1，在我們前文 動態規劃套路詳解 寫過。
我們可以把這個問題轉化為背包問題的描述形式：
有一個背包，最大容量為 amount，有一系列物品 coins，每個物品的重量為 coins[i]，每個物品的數量無限。請問有多少種方法，能夠把背包恰好裝滿？
這個問題和我們前面講過的兩個背包問題，有一個最大的區別就是，每個物品的數量是無限的，這也就是傳說中的「完全背包問題」，沒啥高大上的，無非就是狀態轉移方程有一點變化而已。
下面就以背包問題的描述形式，繼續按照流程來分析。
PS：我認真寫了 100 多篇原創，手把手刷 200 道力扣題目，全部發布在 labuladong的演算法小抄，持續更新。建議收藏，按照我的文章順序刷題，掌握各種演算法套路後投再入題海就如魚得水了。
解題思路
第一步要明確兩點，「狀態」和「選擇」。
狀態有兩個，就是「背包的容量」和「可選擇的物品」，選擇就是「裝進背包」或者「不裝進背包」嘛，背包問題的套路都是這樣。
明白了狀態和選擇，動態規劃問題基本上就解決了，只要往這個框架套就完事兒了：
for 狀態1 in 狀態1的所有取值：
for 狀態2 in 狀態2的所有取值：
for ...
dp[狀態1][狀態2][...] = 計算(選擇1，選擇2...)
第二步要明確 dp 數組的定義。
首先看看剛才找到的「狀態」，有兩個，也就是說我們需要一個二維 dp 數組。
dp[i][j] 的定義如下：
若只使用前 i 個物品，當背包容量為 j 時，有 dp[i][j] 種方法可以裝滿背包。
換句話說，翻譯回我們題目的意思就是：
若只使用 coins 中的前 i 個硬幣的面值，若想湊出金額 j，有 dp[i][j] 種湊法。
經過以上的定義，可以得到：
base case 為 dp[0][..] = 0， dp[..][0] = 1。因為如果不使用任何硬幣面值，就無法湊出任何金額；如果湊出的目標金額為 0，那麼「無為而治」就是唯一的一種湊法。
我們最終想得到的答案就是 dp[N][amount]，其中 N 為 coins 數組的大小。
大致的偽碼思路如下：
int dp[N+1][amount+1]
dp[0][..] = 0
dp[..][0] = 1
for i in [1..N]:
for j in [1..amount]:
把物品 i 裝進背包,
不把物品 i 裝進背包
return dp[N][amount]
第三步，根據「選擇」，思考狀態轉移的邏輯。
注意，我們這個問題的特殊點在於物品的數量是無限的，所以這裡和之前寫的背包問題文章有所不同。
如果你不把這第 i 個物品裝入背包，也就是說你不使用 coins[i] 這個面值的硬幣，那麼湊出面額 j 的方法數 dp[i][j] 應該等於 dp[i-1][j]，繼承之前的結果。
如果你把這第 i 個物品裝入了背包，也就是說你使用 coins[i] 這個面值的硬幣，那麼 dp[i][j] 應該等於 dp[i][j-coins[i-1]]。
首先由於 i 是從 1 開始的，所以 coins 的索引是 i-1 時表示第 i 個硬幣的面值。
dp[i][j-coins[i-1]] 也不難理解，如果你決定使用這個面值的硬幣，那麼就應該關注如何湊出金額 j - coins[i-1]。
比如說，你想用面值為 2 的硬幣湊出金額 5，那麼如果你知道了湊出金額 3 的方法，再加上一枚面額為 2 的硬幣，不就可以湊出 5 了嘛。
綜上就是兩種選擇，而我們想求的 dp[i][j] 是「共有多少種湊法」，所以 dp[i][j] 的值應該是以上兩種選擇的結果之和：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++) {
if (j - coins[i-1] >= 0)
dp[i][j] = dp[i - 1][j]
+ dp[i][j-coins[i-1]];
return dp[N][W]
最後一步，把偽碼翻譯成程式碼，處理一些邊界情況。
我用 Java 寫的程式碼，把上面的思路完全翻譯了一遍，並且處理了一些邊界問題：
int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = amount int[n + 1][amount + 1];
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++)
if (j - coins[i-1] >= 0)
dp[i][j] = dp[i - 1][j]
+ dp[i][j - coins[i-1]];
else
dp[i][j] = dp[i - 1][j];
}
return dp[n][amount];
}
而且，我們通過觀察可以發現，dp 數組的轉移只和 dp[i][..] 和 dp[i-1][..] 有關，所以可以壓縮狀態，進一步降低演算法的空間複雜度：
int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1; // base case
for (int i = 0; i < n; i++)
for (int j = 1; j <= amount; j++)
if (j - coins[i] >= 0)
dp[j] = dp[j] + dp[j-coins[i]];
return dp[amount];
}
這個解法和之前的思路完全相同，將二維 dp 數組壓縮為一維，時間複雜度 O(N*amount)，空間複雜度 O(amount)。
至此，這道零錢兌換問題也通過背包問題的框架解決了。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創文章，手把手帶刷 200 道力扣題目，建議收藏！對應的 GitHub 演算法倉庫 已經獲得了 70k star，歡迎標星！
