經典動態規劃:完全背包問題

讀完本文,你可以去力扣拿下如下題目:

518.零錢兌換II

———–

零錢兌換 2 是另一種典型背包問題的變體,我們前文已經講了 經典動態規劃:0-1 背包問題

希望你已經看過前兩篇文章,看過了動態規劃和背包問題的套路,這篇繼續按照背包問題的套路,列舉一個背包問題的變形。

本文聊的是 LeetCode 第 518 題 Coin Change 2,題目如下:

title

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],其中 Ncoins 數組的大小。

大致的偽碼思路如下:

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,歡迎標星!