經典動態規劃：完全揹包問題

讀完本文，你可以去力扣拿下如下題目： [518.零錢兌換II](https://leetcode-cn.com/problems/coin-change-2) **-----------** 零錢兌換 2 是另一種典型揹包問題的變體，我們前文已經講了 [經典動態規劃：0-1 揹包問題](https://labuladong.gitbook.io/algo)。 **希望你已經看過前兩篇文章**，看過了動態規劃和揹包問題的套路，這篇繼續按照揹包問題的套路，列舉一個揹包問題的變形。 本文聊的是 LeetCode 第 518 題 Coin Change 2，題目如下：  ```java int change(int amount, int[] coins); ``` PS：至於 Coin Change 1，在我們前文 [動態規劃套路詳解](https://labuladong.gitbook.io/algo) 寫過。 **我們可以把這個問題轉化為揹包問題的描述形式**： 有一個揹包，最大容量為 `amount`，有一系列物品 `coins`，每個物品的重量為 `coins[i]`，**每個物品的數量無限**。請問有多少種方法，能夠把揹包恰好裝滿？ 這個問題和我們前面講過的兩個揹包問題，有一個最大的區別就是，每個物品的數量是無限的，這也就是傳說中的「**完全揹包問題**」，沒啥高大上的，無非就是狀態轉移方程有一點變化而已。 下面就以揹包問題的描述形式，繼續按照流程來分析。 PS：**我認真寫了 100 多篇原創，手把手刷 200 道力扣題目，全部發布在 [labuladong的演算法小抄](https://links.jianshu.com/go?to=https%3A%2F%2Flabuladong.gitbook.io%2Falgo%2F)，持續更新**。建議收藏，**按照我的文章順序刷題**，掌握各種演算法套路後投再入題海就如魚得水了。 ### 解題思路 **第一步要明確兩點，「狀態」和「選擇」**。 狀態有兩個，就是「揹包的容量」和「可選擇的物品」，選擇就是「裝進揹包」或者「不裝進揹包」嘛，揹包問題的套路都是這樣。 明白了狀態和選擇，動態規劃問題基本上就解決了，只要往這個框架套就完事兒了： ```python 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` 陣列的大小。 大致的偽碼思路如下： ```python 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]` 的值應該是以上兩種選擇的結果之和**： ```java 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 寫的程式碼，把上面的思路完全翻譯了一遍，並且處理了一些邊界問題： ```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][..]` 有關，所以可以壓縮狀態，進一步降低演算法的空間複雜度： ```java 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)。 至此，這道零錢兌換問題也通過揹包問題的框架解決了。 **＿＿＿＿＿＿＿＿＿＿＿＿＿** 我的 [線上電子書](https://labuladong.gitbook.io/algo) 有 100 篇原創文章，手把手帶刷 200 道力扣題目，建議收藏！對應的 GitHub [演算法倉庫](https://github.com/labuladong/fucking-algorithm) 已經獲得了 70k star，歡迎