leetcode 刷题 log day 44_音音子-的博客-爱代码爱编程
【完全背包问题】完全背包问题是指不限制物品的数量,可以无限制取物品。而 01 背包问题是每个物品只能取一次。
【求放满背包共有几种方法】:
- 递推公式:一般都是
dp[j] += dp[j - weight[i]]
; - 遍历顺序:
1)当求放满的组合共有几种不考虑子集顺序时:先遍历物品后遍历背包(背包正序遍历);
2)当求放满的排列共有几种考虑子集顺序时,要先遍历背包后遍历物品;
3)如果只是求能否放满背包不求几种方法时就哪种遍历顺序都可以。
-
518. 零钱兑换 II
【思路】这道题属于求放满背包有几种组合(不考虑子集顺序),就用先遍历物品后遍历背包的顺序。var change = function(amount, coins) { let dp = new Array(amount + 1).fill(0); dp[0] = 1; for (let i = 0; i < coins.length; i++) { for (let j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; };
-
377. 组合总和 Ⅳ
【思路】这道题属于放满背包求几种排列(考虑子集排序)。var combinationSum4 = function(nums, target) { let dp = new Array(target + 1).fill(0); dp[0] = 1; // 求排列要先遍历背包后遍历物品 for (let i = 0; i <= target; i++) { for (let j = 0; j < nums.length; j++) { if(i >= nums[j]) dp[i] += dp[i - nums[j]]; } } return dp[target]; };
参考代码随想录:https://www.programmercarl.com/