完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

首先再回顾一下01背包的核心代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序（遍历物体，遍历背包容量）是无所谓的！

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

 一遍过。就是完全背包，只是求组合数量。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(5001,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];}
};

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

如果把两个for交换顺序，代码如下：

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

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数！

 

 我原本写法：

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])dp[j]+=dp[j-nums[i]];}}return dp[target];}
};

C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。

改成下面这种，还是报错：

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<long long> 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]+=dp[j-nums[i]];}}return dp[target];}
};

按照题解修改后：还是有些不太懂

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]&&dp[j]<INT_MAX-dp[j-nums[i]])dp[j]+=dp[j-nums[i]];}}return dp[target];}
};