分割等和子序列

416. 分割等和子集

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

思路：

可以认为是对数组中取部分元素，使得加合是所有元素之和的一半（转换成这个问题就会发现本题是标准的01背包问题，就是看每个元素是取还是不取就行）。

则dp[i][j]表示前i个元素，结果是j是否可能存在。dp[i][j]的构成是：

dp[i-1][j],视为第i个元素不取。

dp[i-1][j-num[i]],取第i个元素，但前提是dp[i-1][j-num[i]]得下标合法且存在。

dp[i][j]=dp[i-1][j](一定有) ||dp[i-1][j-num[i]](可能有)。

初始化：

对于i=0时，仅当j=0为真，其余情况均不可能达到。

对于j=0时，对任意i为真，因为一个都不取一定满足总和是j。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
    int n=nums.size();
    int k=0;
    nums.insert(nums.begin(),0);
    for(auto e:nums)
    {
        k+=e;
    }
    if(k%2!=0)
    return false;
    k/=2;
    vector<vector<bool>>dp(n+1,vector<bool>(k+1,false));

    for(int i=0;i<=n;i++)
    {
        dp[i][0]=true;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
           dp[i][j]=dp[i-1][j];
           if(j>=nums[i]&&dp[i-1][j-nums[i]])
           dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
        }
    }

    return dp[n][k];


    }
};

原文地址：https://blog.csdn.net/yyssas/article/details/140497861

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！