代码随想录day44【动态规划】完全背包 零钱兑换 组合总和 Ⅳ

完全背包理论基础

0-1背包 与 完全背包的区别：
0-1背包：一个物品只能拿一次
完全背包：一个物品可以拿多次

完全背包递推公式跟01背包一直。但遍历顺序不为逆序，而是正序遍历（正序遍历可以实现某个物品取多次）。

function maxValue(weight, value, bagWeight) {
  let dp = new Array(bagWeight + 1).fill(0); //初始化

  for (let i = 0; i < weight.length; i++) {
    //物品
    for (let j = weight[i]; j <= bagWeight; j++) {
      //背包
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
    console.log(dp);
  }
  return dp[bagWeight];
}

maxValue([1, 3, 4], [15, 20, 30], 4);
// dp数组打印：
// [ 0, 15, 30, 45, 60 ]
// [ 0, 15, 30, 45, 60 ]
// [ 0, 15, 30, 45, 60 ]

零钱兑换

本质：完全背包的应用。装满一个背包有多少种方法（与之前求目标和类似，但是目标和的物品只能选择一次）
力扣题目链接

1. 含义及递推公式
   dp[j] 装满背包j，有dp[j]种方法
   dp[j] += dp[j - coins[i]];
   2.正序遍历（因为同一物品可以取多次）

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

组合总和

leecode题目链接
与零钱兑换的区别：
本题强调元素的顺序，零钱兑换不强调元素顺序。

遍历顺序若为先物品，后背包：得到组合数
先物品，后背包：得到排列数

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] >= 0) {
                dp[i] += dp[i - nums[j]];
            }
        }
        console.log(dp);
    }

    console.log(dp[target]);
    return dp[target];
};