【LeetCode】【0-1背包】分割等和子集

dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

dp[i]=dp[i] || dp[i-num]

class Solution {
public:
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        for (auto &num: nums)sum += num;
        if (sum & 1)return false;
        int target = sum / 2;
        vector<bool> dp(target + 1);
        dp[0] = true;
        for (auto &num: nums) {
            for (int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
};