完全背包
视频链接
与0-1背包的本质区别：0-1背包每个物品最多用1次，所以只有0（不装包）和1（装包）两种状态；完全背包每个物品不限制使用次数。
代码上的区别：
1.容器遍历顺序可正序：因为不限制使用次数，所以回想一维0-1背包问题在遍历背包时需要倒序，是为了避免物品重复选取，但完全背包没有这个限制，所以倒序改为正序；
2.先后顺序可颠倒：因为0-1背包在遍历背包时要倒序，是为了不导致大容量时只能装一个物品不能装多个物品的情况（因为遍历大容量时，小容量还没遍历，所以递推时调用了还没遍历到的元素），所以在完全背包这里可以正序，从而导致了先后顺序也可以颠倒。
先物品后背包的逻辑解释：对于当前这个物品i，遍历所有容量，判断要不要放这个物品i。同时容量的正序遍历导致了小容量时可能已经放入了物品i，容量增大， 又能放下一个物品i时又放入了一个，实现不限制物品使用次数的效果。
先背包后物品的逻辑解释：对于一个容量j，最后一步放哪个物品都可能，所以再遍历物品，为了找出让价值最大的那个“最后一个物品”。
#include<iostream> using namespace std; #include<vector> int main(){ int m,n; cin>>m>>n; vector<int> weight(m); vector<int> value(m); for(int i=0;i<m;i++){ cin>>weight[i]>>value[i]; } vector<int> dp(n+1,0); for(int i=0;i<m;i++){ for(int j=weight[i];j<=n;j++){ dp[j] = max(dp[j],dp[j-weight[i]]+value[i]); } } cout<<dp[n]<<endl; return 0; }518. 零钱兑换 II
标准的完全背包求装满有多少种方法的问题。
递推公式从最大价值的“dp[j] = max(dp[j],dp[j-weight[i]]+value[i])”换成了“dp[j]+=dp[j-coins[i]]”即可
其余的标准套路和完全背包一致。
解释为什么不需要判别是否装满：因为本身dp[j]的含义就是装满容量j的最大装满方法，初始化dp[0]=1的含义是“要装满容器0只有一种方式：什么都不选”。然后从递推公式来看，上一时刻dp[j]只会加上j-coins[i]的方式数量，比如硬币2，容器3的例子：j=3，dp[3]是0，只能加上dp[3-2]=dp[1];而dp[1]在前面只会加上dp[1-2]，但这是不允许的，所以根本没有遍历到dp[1]，所以dp[3]加了dp[1]也没有，还是0，所以这种递推逻辑就注定了如果容器填不满根本就不会计数。
简单总结：dp[j] 只表示“刚好凑满金额 j 的方法数”，而 dp[j] += dp[j - coins[i]]代表了dp[j]只会从“刚好凑满 j - coins[i]”的方案转移过来，每一次转移都是转移的凑满容量的方案数，所以最终 dp[amount]就是刚好凑满 amount 的方案数。
class Solution { public: int change(int amount, vector<int>& coins) { vector<uint64_t> 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]; } };377. 组合总和 Ⅳ
本题求的是排列数，上一题求的是组合数
区别在于，求组合数需要使用先物品后背包的顺序，求排列数则需要使用先背包后物品的顺序
解释：递推公式dp[j]+=dp[j-nums[i]]本质含义是，从已有方案最后在加一个硬币；
先物品后背包：物品顺序已经固定，如果先遍历物品1，后遍历物品2，那么只会出现物品1-物品2的顺序，不可能出现物品2-物品1的顺序，所以只是求的能组合成最后target的组合数，顺序不算。
先背包后物品：每个金额j都枚举“最后一个硬币是谁”，不同顺序会被分别统计，所以是排列数.
举例：coins = [1, 2]，amount = 3
计算dp[3]：
先遍历 1：dp[3] += dp[2] //dp[2]里面有“1+1”、“2”两种可能，所以最终会出现“1+1+1”和“2+1”两个方案
再遍历 2：dp[3] += dp[1] //dp[1]里面有“1”一种可能，所以还会再加上“1+2”一个方案
最终共“1+1+1”、“2+1”、“1+2”三个方案，出现了“2+1”和“1+2”，顺序不同算作不同的方案数。
class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<uint64_t> 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]; } };
的3个高级技巧)
