完全背包

什么是完全背包？
完全背包和01背包的区别就是，完全背包能将某个物品添加无数次。
在二维dp数组迭代更新中体现为：
01背包dp数组由左上面的数组更新而成；
完全背包do数组由包括本行在内的左边的数组更新而成。
在一维dp数组迭代更新中体现为：
01背包是从后向前遍历；
完全背包是从前向后遍历。

LC 518. 零钱兑换 II

题目链接：LC 518. 零钱兑换 II
思路：完全背包问题，dp二维数组每一行是不用面额的硬币， 每一列是金额，dp数组内的值为有多少种方式得到该总金额（用该行和该行以上的硬币）。
代码：

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

LC 377. 组合总和 Ⅳ

题目链接：LC 377. 组合总和 Ⅳ
思路：要注意顺序不同的也被视为不同的序列。上一题为组合问题，本题为排列问题。都是完全背包问题，但是这两道题的遍历顺序不同。上一题遍历顺序是先遍历物品再遍历背包，本题的遍历顺序为先遍历背包再遍历物品。
代码：

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1, 0);dp[0] = 1;for(int i=1; i<target+1; i++){//先遍历背包for(int j=0; j<nums.size(); j++){//再遍历物品if(i-nums[j]>=0&&dp[i]<INT_MAX-dp[i-nums[j]]){//后面是防止两数相加过大dp[i] += dp[i-nums[j]];}}}return dp.back();}
};