本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目来源

本题来源为：

Leetcode416. 分割等和子集

题目描述

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

算法原理

这道题我们可以将其进行转化，转化成选择一些数来能让他等于sum/2；


还可以再判断一下：

1.状态表示

经验+题目要求

对于本题而言就是：

dp[i][j]表示：从前i个物品中挑选，所有选法中，能否凑出j这个数

2.状态转移方程

跟01背包问题方法分析一致：

因此状态方程为：

dp[i][j]=dp[i-1][j];
 if(j>=nums[i-1])
dp[i][j]=dp[i][j]||dp[i-1][j-nums[i-1]];

3.初始化

跟01背包问题的初始化一样：

4.填表顺序

从上往下填写每一行

5.返回值

dp[n][sum/2]

代码实现

动态规划的代码基本就是固定的四步：

1.创建dp表
2.初始化
3.填表
4.返回值

本题完整代码实现：

class Solution 
{
public:
    bool canPartition(vector<int>& nums) 
    {

        int n=nums.size();
        int sum=0;
        //遍历
        for(auto x:nums)
        sum+=x;
        if(sum%2==1)
        return false;

        int aim=sum/2;
        //创建dp表
        vector<vector<bool>> dp(n+1,vector<bool>(aim+1));
        //初始化
        for(int i=0;i<=n;i++)
            dp[i][0]=true;
        //填表
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=aim;j++)
            {
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1])
                    dp[i][j]=dp[i][j]||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(auto x:nums)
        sum+=x;
        if(sum%2==1)
        return false;

        int aim=sum/2;
        //创建dp表
        vector<bool> dp(aim+1);
        //初始化
        dp[0]=true;
        //填表
        for(int i=1;i<=n;i++)
        {
            for(int j=aim;j>=nums[i-1];j--)
            {
                    dp[j]=dp[j]||dp[j-nums[i-1]];
            }
        }
        return dp[aim];
    }
};