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