代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

动态规划：完全背包理论基础

代码随想录 (programmercarl.com)

动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

完全背包中的物品可以添加多次，所以要从小到大遍历：

// 先遍历物品，再遍历背包
for (int i = 0; i < weight.length; i++) { // 遍历物品
    for (int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        // dp[j]表示背包容量为j时的最大价值
        // dp[j - weight[i]]表示背包容量为j减去当前物品重量时的最大价值
        // value[i]表示当前物品的价值
        // Math.max(dp[j], dp[j - weight[i]] + value[i])表示在不超过背包容量的情况下，选择装入当前物品或者不装入当前物品的最大价值
    }
}

518.零钱兑换II

518. 零钱兑换 II - 力扣（LeetCode）

代码随想录 (programmercarl.com)

动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 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

注意，你可以假设：

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

动规五部曲：

1、确定dp数组以及下标的含义：

dp[j] 凑成总金额j的货币组合数为dp[j];

2、确定递推公式：dp[j]就是所有的dp[j-coins[i]]相加，所以dp[j] += dp[j - coins[i]]

3、dp数组如何初始化：dp[0]=1;

4、确定遍历顺序：求组合是外层for循环遍历物品，内层for循环遍历背包；求排列就是外层for循环遍历背包，内层for循环遍历物品。

5、举例推导dp数组：输入：amounts=5, coins=[1,2,5]

综合代码：

class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

class Solution {
    // 定义一个名为Solution的类
    public int change(int amount, int[] coins) {
        // 创建一个名为change的公共方法，接受一个整数amount和一个整数数组coins作为参数，并返回一个整数
        int[] dp = new int[amount + 1];
        // 创建一个名为dp的整数数组，其长度为amount加1，用于存储不同金额的组合数量
        dp[0] = 1;
        // 初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        for (int i = 0; i < coins.length; i++) {
            // 遍历硬币数组
            for (int j = coins[i]; j <= amount; j++) {
                // 遍历金额，从当前硬币面额开始，直到目标金额
                dp[j] += dp[j - coins[i]];
                // 更新dp数组中的值，当前金额j的组合数量等于上一个金额(j - coins[i])的组合数量加上当前硬币的组合数量
            }
        }
        return dp[amount];
        // 返回目标金额amount的组合数量
    }
}