代码随想录训练营二刷第四十六天 | 完全背包 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];}
}

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