建设厅查询网站,建站网络建立科技开发,淮安房产网,东营网约车最新消息代码随想录训练营二刷第四十六天 | 518. 零钱兑换 II 377. 组合总和 Ⅳ
一、518. 零钱兑换 II
题目链接#xff1a;https://leetcode.cn/problems/coin-change-ii/ 思路#xff1a;完全背包求组合数#xff0c;递推公式dp[j]dp[j-nums[i]]。 求组合数#xff0c;物品在外…代码随想录训练营二刷第四十六天 | 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[amount1];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[target1];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];}
}
