代码随想录训练营day44|完全背包；518、零钱兑换 II；377、组合总和 Ⅳ

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

代码模板：

//先遍历物品，再遍历背包
private static void testCompletePack(){int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWeight = 4;int[] dp = new int[bagWeight + 1];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]);}}for (int maxValue : dp){System.out.println(maxValue + "   ");}
}//先遍历背包，再遍历物品
private static void testCompletePackAnotherWay(){int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWeight = 4;int[] dp = new int[bagWeight + 1];for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量for (int j = 0; j < weight.length; j++){ // 遍历物品if (i - weight[j] >= 0){dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);}}}for (int maxValue : dp){System.out.println(maxValue + "   ");}
}

518、零钱兑换 II

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

示例 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 位符号整数

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

这里的遍历顺序是有要求的。

377、组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

• nums = [1, 2, 3]
• target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.length; j++) {if (i >= nums[j]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
}

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。