leetcode 刷题 log day 44

【完全背包问题】完全背包问题是指不限制物品的数量，可以无限制取物品。而 01 背包问题是每个物品只能取一次。
【求放满背包共有几种方法】：

1. 递推公式：一般都是 dp[j] += dp[j - weight[i]]；
2. 遍历顺序：
   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];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

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

参考代码随想录：https://www.programmercarl.com/