leetcode动态规划—背包系列（二）

416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

这道题可以用01背包来求解，也就是数组中的数能否能装下sum/2的包，即dp[sum/2]是否为true.

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        const int sum = std::accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;
        vector<int> dp(sum + 1, 0);
        dp[0] = 1;
        for (const int num : nums) {
            for (int i = sum/2; i >= 0; --i)
                if (dp[i]) dp[i+num] = 1;
            if (dp[sum / 2]) return true;
        }
        return false;
    }
};

在评论区看到一个用bitset来做的，虽然还不太懂，但还是记录下来回头来看再做补充。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        if(nums.size()<2)   return false;
        
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum&1)  return false;
        
        bitset<10001> bits(1);
        for (auto n : nums) bits |= bits << n;
        return bits[sum >> 1];
    }
}

377. 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

这是一道涉及顺序的完全背包。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        if(nums.empty()) return 0;
        vector<unsigned long long> dp(target+1,0);//用int会溢出
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(auto num:nums){
                if(i>=num) dp[i]+=dp[i-num];
            }
        }
        return dp.back();
    }
};