代码随想录算法训练营第44天 | 完全背包理论基础, 518.零钱兑换 II, 377.组合总和 Ⅳ

完全背包理论基础

代码随想录链接

完全背包和0-1背包的区别在于， 0-1背包问题中每个待取物品只有一个, 只存在被取与不取两个状态, (所以才是0-1背包). 而完全背包问题中, 每一件物品都有无数件, 除了被取与不取两个状态外还有很多种取了不同件的状态.

完全背包与0-1区别在于遍历顺序上, 完全背包的遍历方式主要为:

// 外层for循环遍历物品, 内层for循环逆向遍历背包容量
for (int i = 0; i < weight.size(); i++)
    for (int j = bagSize; j >= weight[i]; j--)
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

而完全背包的遍历方式:

// 外层for循环遍历物品, 内层for循环正向遍历背包容量
for (int i = 0; i < weight.size(); i++)
    for (int j = weight[i]; j <= bagSize; j++)
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

518.零钱兑换 II

代码随想录链接

题目

LeetCode-518.零钱兑换 II

给定不同面额的硬币和一个总金额, 使用任意数量的硬币来凑成总金额, 求可以凑成的组合数.

分析

这道题就是完全背包问题, 且是组合问题, 不是排序问题.

动态规划五部曲:

• 确定dp数组及下标的含义

  dp[j]: 凑成j金额的组合数为dp[j]

• 确定递推公式

  dp[j]就是所有dp[j - coins[i]]的总和

  \[dp[j] += dp[j -coins[i]]\]

• dp数组的初始化

  凑够金额为0的组合只有一种, 所以\(dp[0] = 1\).

• 遍历顺序

  这里求的是组合数, 应该先遍历物品, 后遍历背包

  for (int i = 0; i < coins.size(); i++)
    for (int j = coins[i]; j <= amount; j++)
        dp[j] += dp[j - coins[i]];

  也给出求排列数的方法:

  for (int j = 0; j <= amount; j++)
    for (int i = 0; i < coins.size(); i++)
        if (j - coins[i] >= 0)
            dp[j] += dp[j - coins[i]];

• 举例推导

题解

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++)
            for (int j = coins[i]; j <= amount; j++)
                dp[j] += dp[j - coins[i]];
        return dp[amount];
    }
};

377.组合总和 Ⅳ

代码随想录链接

题目

LeetCode-377. 组合总和 Ⅳ

给定一个不重复的正整数数组和一个数值, 找出和为给定数值的排列数.

分析

这道题就是完全背包的排列问题了.

动态规划五部曲:

• 确定dp数组及下标含义

  dp[j]代表和为j时, 有多少种排列

• 确定递推公式

  求装满背包的方法时, 递推公式一般是

  \[dp[j] += dp[j - nums[i]]\]

• dp数组的初始化

  dp[0] = 1, 不仅是因为凑够0只有一种方法, 更是为了在递归其他dp[j]时让数值有意义.

• 遍历顺序

  本题要求排列数, 和上面提到的求排列的方法应当对应起来

  // 外层for循环遍历背包容量, 内层for循环遍历物品, 且因为求排列数, 两者都要正向遍历
  for (int j = 0; j <= target; j++)
    for (int i = 0; i < nums.size(); i++)
        if (j - nums[i] >= 0)
            dp[j] += dp[j - nums[i]];

• 举例推导

题解

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int j = 0; j <= target; j++)
            for (int i = 0; i < nums.size(); i++)
                if (j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]])
                    dp[j] += dp[j - nums[i]];
        return dp[target];
    }
};