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];
    }
}