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

题目链接：416. 分割等和子集

判断数组能否被分成两个和相等的子数组，先求数组的和sum，即变成能不能找到一个组合的和是sum/2，每个数最多只能被选择一次，即0-1背包问题

0-1背包状态转移方程：如果选择，那么空间减少，价值增加，dp[i]为空间为i的最大价值

代码语言：javascript复制

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

本问题：dp[i]为是否存在和为i的子集，如果选择当前元素，变成是否存在和为i-num的子集

代码语言：javascript复制

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

特别注意如果sum是奇数，那么sum/2不是整数肯定不存在

代码语言：javascript复制

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];
    }
};

sum target 数组 dp leetcode

0 人点赞