完全背包问题求组合数和排列数

518. 零钱兑换 II

这个是完全背包问题的典型应用，由于只是求个数，不涉及到零钱排列情况不一样算两次的情况，所以两层for循环，外层遍历物品，内层遍历背包。

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

377. 组合总和 Ⅳ

这个与上面一题唯一不同的一点就是有序，顺序不同算两次，所以这里两层for循环的遍历顺序是外层遍历背包，内层遍历物品。

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
    
        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];
    }
}

关于背包问题，参考文章。