代码随想录Day46

518.零钱兑换||

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

思路：组合问题，应该用的递推公式跟目标和是一样的

尝试（参考目标和递推公式，以及完全背包遍历for循环，AC）

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        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 {
    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];
    }
}

小结

• dp[j]：凑成总金额j的货币组合数为dp[j]
• 求装满背包有几种方法，公式都是：dp[j] += dp[ j - nums[i] ];
• dp[0] = 1是 递归公式的基础。

377.组合总和IV

题目：377. 组合总和 Ⅳ - 力扣（LeetCode）

思路：有点难的是，这个是要考虑排序的，不同顺序会被视为不同的组合，想不出来

答案

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

小结

1. dp[i]: 凑成目标正整数为i的排列个数为dp[i]
2. 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
3. 如果求排列数就是外层for遍历背包，内层for循环遍历物品。