题目来源
本题来源为：
题目描述
给你一个 只包含正整数 的 非空 数组 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]; } };
