力扣 -- 416. 分割等和子集（01背包问题）

解题步骤：

参考代码：

未优化代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(const auto& e:nums)
        {
            sum+=e;
        }
        if(sum%2==1)
        {
            return false;
        }
        int aim=sum/2;
        //多开一行，多开一列
        vector<vector<bool>> dp(n+1,vector<bool>(aim+1));
        //初始化
        for(size_t i=0;i<=n;i++)
        {
            dp[i][0]=true;
        }
        for(size_t i=1;i<=n;i++)
        {
            for(size_t j=1;j<=aim;j++)
            {
                dp[i][j]=dp[i-1][j]||((j>=nums[i-1])&&dp[i-1][j-nums[i-1]]);
            }
        }
        return dp[n][aim];
    }
};

优化后的代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(const auto& e:nums)
        {
            sum+=e;
        }
        if(sum%2==1)
        {
            return false;
        }
        int aim=sum/2;
        //多开一个位置
        vector<bool> dp(aim+1);
        //初始化
        dp[0]=true;

        for(size_t i=1;i<=n;i++)
        {
            //一定记得要从右往左填写
            for(size_t j=aim;j>=nums[i-1];j--)
            {
                dp[j]=dp[j]||dp[j-nums[i-1]];
            }
        }
        return dp[aim];
    }
};

你学会了吗？？？

标签：力扣 -- 416. 分割等和子集（01背包问题）