代码随想录训练营二刷第四十六天 | 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

代码随想录训练营二刷第四十六天 | 518. 零钱兑换 II 377. 组合总和 Ⅳ

一、518. 零钱兑换 II

题目链接：https://leetcode.cn/problems/coin-change-ii/
思路：完全背包求组合数，递推公式dp[j]+=dp[j-nums[i]]。
求组合数，物品在外，背包在内。求排列数，背包在外，物品在内。

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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

二、377. 组合总和 Ⅳ

题目链接：https://leetcode.cn/problems/combination-sum-iv/
思路：这题就是求排列数，背包在外，物品在内。

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 (nums[j] <= i) {
                    dp[i] += dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14