代码随想录day44：动态规划part06

完全背包理论

遍历顺序：

• 0，1背包的一维dp[j]，一定是外层嵌套物品，内层背包容量倒序
• 完全背包的一维dp[j]，嵌套顺序无所谓，背包容量要正序
  但如果题目稍稍有点变化，就会体现在遍历顺序上

  518.零钱兑换

  钱币数量不限，所以完全背包问题，但是不是求得背包装的最大价值，而是组合数。
  注意：组合数不等于排列数
  动规五部曲：1.dp[j]凑成金额j的货币数
  2.递推公式dp[j]+=dp[j-coin[i]]跟之前组合数的公式一样
  3.初始化：首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]。
  4.遍历顺序：
  由于这道题求得是组合数，顺序不同但是集合相同是同一种情况。所以遍历顺序不能像单纯的完全背包物品和背包容量可以无所谓嵌套内外。
  而是应该外层物品，内层背包容量：
  注意此表格是用二维展示一维每次物品从0到2放入背包的情况。这时候，背包放入物品没有顺序

    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];
    }
1
2
3
4
5
6
7
8
9
10

如果外层背包容量，内层物品嵌套，背包容量为1时，可以放下物体0，有1种。
背包容量为2时，可以放下物品0，1，有两种：1，1和2
背包容量为3时，dp[3]=dp[2]+dp1 +（在1里放入2）出现重复

377.组合总和四

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int sum=0;
        /*
        for(int i=0;i
        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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20