代码随想录训练营 Day44

今日任务

完全背包理论基础
518.零钱兑换Ⅱ
377.组合总和Ⅳ
语言：Java

完全背包理论基础

对于简单的纯完全背包问题，因为物品的数量是没有限制的，所以要从前到后遍历；内外层的循环顺序可以改变，也就是先遍历物品/背包都可以；但是应用题中会有附加条件限制，不会这么自由。

518. 零钱兑换Ⅱ

链接：https://leetcode.cn/problems/coin-change-ii/
和纯完全背包问题的不同：这道题是求不同的组合数，所以要考虑元素相等的组合不能重复计数的问题，比如组合{1,5}和{5,1}就属于同一种组合；如果先遍历背包再遍历物品，那么上述两种组合都会算入结果，但这是不对的，所以应该先遍历物品再遍历背包。

class Solution {
    public int change(int amount, int[] coins) {
        //1.确定dp数组及下标含义: dp[j]代表总金额为j的硬币有dp[j]种方法
        //2.递归公式: dp[j] += dp[j - coins[i]]
        //3.初始化: dp[0]=1
        //4.遍历顺序: 从小到大
        //5.打印dp数组
        int[] dp = new int[amount + 1];
        dp[0] = 1; //attention，可以认为只有空集一种取法
        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. 组合总和Ⅳ

链接：https://leetcode.cn/problems/combination-sum-iv/
和纯完全背包问题的不同：这道题是求排列的总个数，也就是说元素相同但顺序不同算作两个结果，此时应该外层遍历背包，内层遍历物品（从前到后遍历）。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        //1.明确dp数组及下标含义
        //2.递归公式
        //3.初始化
        //4.遍历顺序
        //5.打印dp数组
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int j = 1; j <= target; j++){
            for(int i = 0; i < nums.length && nums[i] <= j; i++){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

改进：还是for终止循环条件和循环内if的区别，这是第二次碰到这个问题了。如果在for的终止循环条件加了判断，就会漏掉元素没有按照严格递增排序的情况（[3,2,1,4], target=4）

class Solution {
    public int combinationSum4(int[] nums, int target) {
        //1.明确dp数组及下标含义
        //2.递归公式
        //3.初始化
        //4.遍历顺序
        //5.打印dp数组
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int j = 1; j <= target; j++){
            for(int i = 0; i < nums.length; i++){
                if(j >= nums[i]){
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}