讀完本文垄潮，你可以去力扣拿下如下題目：
-----------
零錢兌換 2 是另一種典型背包問題的變體，我們前文已經(jīng)講了 經(jīng)典動態(tài)規(guī)劃：0-1 背包問題从橘。
希望你已經(jīng)看過前兩篇文章，看過了動態(tài)規(guī)劃和背包問題的套路，這篇繼續(xù)按照背包問題的套路，列舉一個背包問題的變形狈蚤。
本文聊的是 LeetCode 第 518 題 Coin Change 2，題目如下：
int change(int amount, int[] coins);
PS：至于 Coin Change 1划纽，在我們前文 動態(tài)規(guī)劃套路詳解 寫過脆侮。
我們可以把這個問題轉(zhuǎn)化為背包問題的描述形式：
有一個背包，最大容量為 amount勇劣，有一系列物品 coins靖避，每個物品的重量為 coins[i]潭枣，每個物品的數(shù)量無限。請問有多少種方法幻捏，能夠把背包恰好裝滿盆犁？
這個問題和我們前面講過的兩個背包問題，有一個最大的區(qū)別就是篡九，每個物品的數(shù)量是無限的谐岁，這也就是傳說中的「完全背包問題」，沒啥高大上的榛臼，無非就是狀態(tài)轉(zhuǎn)移方程有一點變化而已伊佃。
下面就以背包問題的描述形式，繼續(xù)按照流程來分析沛善。
PS：我認真寫了 100 多篇原創(chuàng)航揉，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄金刁，持續(xù)更新帅涂。建議收藏，按照我的文章順序刷題尤蛮，掌握各種算法套路后投再入題海就如魚得水了媳友。
解題思路
第一步要明確兩點，「狀態(tài)」和「選擇」产捞。
狀態(tài)有兩個庆锦，就是「背包的容量」和「可選擇的物品」，選擇就是「裝進背包」或者「不裝進背包」嘛轧葛，背包問題的套路都是這樣。
明白了狀態(tài)和選擇艇搀，動態(tài)規(guī)劃問題基本上就解決了尿扯，只要往這個框架套就完事兒了：
for 狀態(tài)1 in 狀態(tài)1的所有取值：
for 狀態(tài)2 in 狀態(tài)2的所有取值：
for ...
dp[狀態(tài)1][狀態(tài)2][...] = 計算(選擇1，選擇2...)
第二步要明確 dp 數(shù)組的定義焰雕。
首先看看剛才找到的「狀態(tài)」衷笋，有兩個，也就是說我們需要一個二維 dp 數(shù)組矩屁。
dp[i][j] 的定義如下：
若只使用前 i 個物品辟宗，當(dāng)背包容量為 j 時，有 dp[i][j] 種方法可以裝滿背包吝秕。
換句話說泊脐，翻譯回我們題目的意思就是：
若只使用 coins 中的前 i 個硬幣的面值，若想湊出金額 j烁峭，有 dp[i][j] 種湊法容客。
經(jīng)過以上的定義秕铛，可以得到：
base case 為 dp[0][..] = 0， dp[..][0] = 1缩挑。因為如果不使用任何硬幣面值但两，就無法湊出任何金額；如果湊出的目標(biāo)金額為 0供置，那么“無為而治”就是唯一的一種湊法谨湘。
我們最終想得到的答案就是 dp[N][amount]，其中 N 為 coins 數(shù)組的大小芥丧。
大致的偽碼思路如下：
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]
第三步紧阔，根據(jù)「選擇」，思考狀態(tài)轉(zhuǎn)移的邏輯娄柳。
注意寓辱，我們這個問題的特殊點在于物品的數(shù)量是無限的，所以這里和之前寫的背包問題文章有所不同赤拒。
如果你不把這第 i 個物品裝入背包秫筏，也就是說你不使用 coins[i] 這個面值的硬幣，那么湊出面額 j 的方法數(shù) dp[i][j] 應(yīng)該等于 dp[i-1][j]挎挖，繼承之前的結(jié)果这敬。
如果你把這第 i 個物品裝入了背包，也就是說你使用 coins[i] 這個面值的硬幣蕉朵，那么 dp[i][j] 應(yīng)該等于 dp[i][j-coins[i-1]]崔涂。
首先由于 i 是從 1 開始的，所以 coins 的索引是 i-1 時表示第 i 個硬幣的面值始衅。
dp[i][j-coins[i-1]] 也不難理解冷蚂，如果你決定使用這個面值的硬幣，那么就應(yīng)該關(guān)注如何湊出金額 j - coins[i-1]汛闸。
比如說蝙茶，你想用面值為 2 的硬幣湊出金額 5，那么如果你知道了湊出金額 3 的方法诸老，再加上一枚面額為 2 的硬幣隆夯，不就可以湊出 5 了嘛。
綜上就是兩種選擇别伏，而我們想求的 dp[i][j] 是「共有多少種湊法」蹄衷，所以 dp[i][j] 的值應(yīng)該是以上兩種選擇的結(jié)果之和：
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];
}
而且调卑，我們通過觀察可以發(fā)現(xiàn)抡砂，dp 數(shù)組的轉(zhuǎn)移只和 dp[i][..] 和 dp[i-1][..] 有關(guān)，所以可以壓縮狀態(tài)恬涧，進一步降低算法的空間復(fù)雜度：
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 數(shù)組壓縮為一維，時間復(fù)雜度 O(N*amount)溯捆，空間復(fù)雜度 O(amount)丑搔。
至此，這道零錢兌換問題也通過背包問題的框架解決了提揍。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章啤月，手把手帶刷 200 道力扣題目，建議收藏劳跃！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star谎仲，歡迎標(biāo)星！
