完全背包的理论基础：
因为一个物品可以取多次，因此遍历顺序和0-1背包不同。
0-1背包遍历背包的时候是倒序，这里是顺序，允许重复，且物品和背包可以交换遍历顺序。
完全背包先遍历物品，再遍历背包是组合问题，物品中没有重复
先遍历背包，再遍历物品时排列问题，物品中会有重复，比如1，2和2,1
算法思想：
一个物品可以使用多次，求装满这个背包有多少次。完全背包问题。
递推公式有点类似于爬楼梯，最后一步可以有1-n步的情况，因此递推公式为:
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];
}
};
算法思想：
完全背包中的排列问题，先遍历背包，再遍历物品。可以类比于爬楼梯，爬楼梯是个排列问题
代码：
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];
}
};
