Complete knapsack problem to find the number of combinations and permutations

518. 零钱兑换 II

This is a typical application of the complete knapsack problem,Because it's just asking for numbers,It does not involve the case where the arrangement of the change is different and counted twice,所以两层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. 组合总和 Ⅳ

The only difference between this one and the one above is the ordering,Different order counts twice,So here are two layersforThe traversal order of the loop is 外层遍历背包,内层遍历物品.

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

关于背包问题,参考文章.