本文主要是介绍代码随想录算法训练营第四十三天|LeetCode518 零钱兑换Ⅱ、LeetCode377 组合总和Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
01背包与完全背包：
01背包与完全背包最大的区别在于01背包物品每个只能取一次而完全背包每个物品可以取无数次，这也就导致了我们内层for循环中的不同。具体体现为：因为01背包每个物品仅用一次，所以我们将背包从大到小(倒序)遍历；而完全背包是可以多次添加那么需要将背包从小到大(正序)遍历。
题1：
指路：518. 零钱兑换 II - 力扣（LeetCode）
思路与代码：
凑金币，典型的背包问题，当看到假设每一种面额的硬币有无限个时，进一步判断得到这是一个完全背包问题。首先定义一个数组dp[j]，其含义为当背包容量为j时，货币组合数为dp[j]，换句话说dp[j]是凑成总金额为j的货币组合数；其次我们尝试得出递推公式，此处为装满背包，方法公式为dp[j]=dp[j]+dp[j-nums[i]]，放在此处就是dp[j]+=dp[j-coins[i]]；然后我们对其进行初始化，当总金额为0时，此时有1种方法得到金额0，也就是dp[0]=1(略微牵强，其实是因为如果初始化为0的话后面没办法推导了)。接着我们确定遍历顺序，题目中给出的问题为“组合”，与排列不同，也就是说{1, 2}和{2, 1}是一种情况，而外层遍历物品内层遍历背包满足这一条件。最后打印总金额的组合数即可。代码如下：
class Solution {
public:int change(int amount, vector<int>& coins) {// 定义一个dp数组，含义为当面额为j时，有dp[j]种组合方式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];}
};题2：
指路：377. 组合总和 Ⅳ - 力扣（LeetCode）
思路与代码：
我们根据题意中{1, 2, 1}和{1, 1, 2}是两种情况得到这是一个排列问题，对于这个问题，我们在上一题中提到过，排列问题需要外层for循环先遍历背包之后内层for遍历物品。当背包容量大于物品重量且容量为j时满足条件。而我们C++中的测试用例有的相加超过了int范围，需要再加上范围条件，也就是dp[j] < INT_MAX - 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 i = 0; i < nums.size(); i++) {// for (int j = nums[i]; j <= target; j++) {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];}
};这篇关于代码随想录算法训练营第四十三天|LeetCode518 零钱兑换Ⅱ、LeetCode377 组合总和Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
