代码随想录算法训练营第四十四天|完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ

完全背包

题目链接：52. 携带研究材料（第七期模拟笔试） (kamacoder.com)

思路：完全·背包问题和01背包的区别在于同一个物品可以被重复放入，在代码里的区别就是内部遍历背包的for循环由倒序变成了正序。而且如果我们压缩了一维的话，如我的做法，两个for循环的顺序也是无所谓的。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,v;
    cin>>n>>v;
    vector<int> dp(v+1,0);
    vector<vector<int>> bag(n+1,vector<int>(2,0));
    for(int i=0;i<n;i++){
        cin>>bag[i][0]>>bag[i][1];
    }
    for(int j=0;j<n;j++){
        for(int k=1;k<=v;k++){
            if(k>=bag[j][0])
                dp[k]=max(dp[k],dp[k-bag[j][0]]+bag[j][1]);
        }
    }
    
    cout<<dp.back();
    return 0;
}

零钱兑换 II 

题目链接：518. 零钱兑换 II – 力扣（LeetCode）

思路：记住状态转移方程不是dp[j]=dp[j-coins[i]]+1而是dp[j]+=dp[j-coins[i]];

不过值得注意的是：

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

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=1;j<=amount;j++){
                if(j>=coins[i])dp[j]+=dp[j-coins[i]];
            }
        }
        return dp.back();
    }
};

组合总和 Ⅳ  

题目链接：377. 组合总和 Ⅳ – 力扣（LeetCode）

思路：用long都能超，我真是服了这个样例了。

避免超限制的方法：加一个判断dp[j] < INT_MAX - dp[j - nums[i]]因为这一题动态规划有个坑，就是答案保证最终答案的组合数在32位范围内，但是如果在taraget之前的数字组合数是可能超过INT_MAX的，甚至更大，但因为最终答案不会超过，所以target肯定不会利用到这些超过INT_MAX的数据的，所以忽略掉那些会超过INT_MAX的就可以。

但是莫名其妙的改成unsigned int 就能通过样例，long就不行。

值得注意的是尽管本题问的是组合数，但是事实上答案是排列数目，因此如上一题所说，我们要先遍历背包容量，再遍历物品。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int j = 1; 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.back();
    }
};