代码随想录算法训练营第四十四天|完全背包、LeetCode518 零钱兑换、LeetCode 377组合总和IV

完全背包

思路：相比于0-1背包，完全背包中的物品是可以重复使用的，在代码上，背包的循环是从前往后的。在面对常规求完全背包最大价值的问题中，物品的循环和背包的循环的顺序是可以变换的，一般是先遍历物品再遍历背包。在考虑组合排列问题时，如果考虑组合问题，先遍历物品再遍历背包，如果考虑排列问题，先遍历背包，后遍历物品。

518.零钱兑换

思路：这道题跟之前01背包一道题的递归函数相同，首先确定dp数组及其下标的含义，dp[j]代表装满容量为j的背包最多有dp[j]中方法。递推公式为dp[j]+=dp[j-coins[i]]，很容易理解，装满j容量的背包的方法数为装满j-coins[i]容量的方法数的和，因为装满j-coins[i]容量的方法数，只需要再加上个coins[i]就是容量j，因此对所有j-coins[i]容量的方法数求和即为dp[j]。初始化dp数组，求方法数的问题，初始化dp[0]=1，当背包容量为0时，什么也不装，也是一种方法，如果dp[0]初始化为0了，后续的递推都为0。遍历顺序，由于是完全背包问题，因此在遍历背包时从前到后，物品可以重复利用，因为是组合问题，因此先遍历物品再遍历背包。打印dp数组，可以用于debug。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //确定dp数组及其下标含义 dp[j]代表装满容量j的背包的方法数
        //递推公式dp[j]+=dp[j-cions[i]];
        //初始化dp数组 dp[0]=1; 装满容量为0的背包的方法数为1，如果为0后续递推所有都为0；
        //遍历顺序，由于物品可以重复使用，正向遍历
        //打印dp数组，可以用于debug
        vector<int> dp(amount+1,0);
        dp[0]=1;
        for(int i = 0;i<coins.size();i++)// 先遍历物品再遍历背包是组合问题， 因为在每个物品的循环里都是先放coins[1]在考虑放coins[2],即可能会出现{1，1，2}的情况，但绝不会出现{1,2,1}的情况。
        //先遍历背包再遍历物品是排列问题，因为dp[j]是基于dp[j-coins[i]]来计算的，dp[j-coins[i]]中可能包含了{1，2}但在dp[j]的循环中，又可能会加入了{1}出现{1，2，1}的情况
        {
            for(int j = coins[i];j<=amount;j++)
            {
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

377.组合总和IV

思路：该问题中顺序不同的序列被视作不同的组合，其实就是排列问题。也是求方法数，因此与上一题不同的地方就是遍历顺序，需要先遍历背包，再遍历物品数。第一遍跑代码的时候int溢出了，dp[target]之前的索引有溢出的数值，因此在if判断中加了 dp[j]<=INT_MAX-dp[j-nums[i]]，可以解决溢出问题。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //确定dp数组及其下标含义 dp[j]为装满背包容量j的方法数。
        //递推公式 dp[j] +=dp[j-nums[i]];
        //初始化dp数组 dp[0]=1;
        //遍历顺序，由于顺序不同的序列被视作不同的组合，因此这道题是求排列数，应先遍历背包后遍历物品，从前往后遍历
        //打印dp数组，可以用于debug
        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]&&dp[j]<=INT_MAX-dp[j-nums[i]])
                {
                    dp[j]+=dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
};