518.零錢兌換Ⅱ

目錄

• 518.零錢兌換Ⅱ
  • 題目
  • 題解

給你一個整數數組 coins 表示不同面額的硬币，另給一個整數 amount 表示總金額。

請你計算并傳回可以湊成總金額的硬币組合數。如果任何硬币組合都無法湊出總金額，傳回 0 。

假設每一種面額的硬币有無限個。

題目資料保證結果符合 32 位帶符号整數。

示例 1：

輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋：有四種方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
           

示例 2：

輸入：amount = 3, coins = [2]
輸出：0
解釋：隻用面額 2 的硬币不能湊成總金額 3 。
           

示例 3：

輸入：amount = 10, coins = [10] 
輸出：1
           

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/coin-change-2

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

從一個數組中按一定的選取方式得到目标target，那麼嘗試将題目進行轉化為背包問題。

這裡的物品可以重複選擇，那麼背包應該是完全背包。

背包的容量是amount，物品是coins[i],物品的重量是coins[i]

1.确定dp數組以及下标的含義

dp[j] 表示填滿背包容量j有dp[j]種方法。

2.确定遞推公式

dp[j]如何推出來？

• 填滿j-nums[i]的背包有dp[j-coins[i]]種方法，也就是如果目前coins[i]放入背包那麼就有dp[j-coins[i]]種方法
• 之前填滿容量為j背包的方法數，也就是目前coins[i]不放進背包

說的更加直白一點，那就是用前k的硬币湊齊金額i，要分為兩種情況計算，

一種是沒有用第K個硬币就湊齊了，一種是前面已經湊到了i-coins[k]，現在就差第k個硬币了。

兩種方法都可以選擇，那麼dp[j] = dp[j] + dp[j-coins[i]]

3.dp數組如何初始化

dp[0] = 1,有一種裝法

4.确定周遊順序

先周遊物品，再周遊背包

for(int coin : coins){
            for(int j = coin;j<=amount;j++){
                 dp[j] += dp[j-coin];
            }
 }
           

這裡的周遊順序是不可以變的。

先枚舉金額，代表對于金額來說每次硬币循環都是可以的，1+2和2+1代表了兩種方案，也就是排列問題。

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int coin : coins){
            for(int j = coin;j<=amount;j++){
                 dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
}