原题地址
https://leetcode.com/problems/partition-equal-subset-sum/description/
题意
给一个非空数组，把数组划分成和相同的两部分
思路
对数组求和，若是奇数返回false，若是偶数自底向上建表
做的时候遇到的问题：一开始建表忘记先全都置成false了
代码
class Solution {
public:
int Sum(vector<int> & nums){
int result=0;
for(int i =0;i<nums.size();i++){
result+=nums[i];
}
return result;
}
bool canPartition(vector<int>& nums) {
int sum = Sum(nums);
if(sum%2!=0){
return false;
}
int target = sum/2;
int n = nums.size();
bool dp[target+1][n+1];
memset(dp,false,sizeof(bool)*(target+1)*(n+1));
for(int i =0;i<=n;i++){
dp[0][i]=true;
}
for(int i =1;i<=target;i++){
dp[i][0]=false;
}
for(int i =1;i<=target;i++){
for(int j =1;j<=n;j++){
if(i>=nums[j-1]){
dp[i][j]= dp[i-nums[j-1]][j-1];
}
if(dp[i][j]){
for(int k =j+1;k<=n;k++){
dp[i][k]=true;
}
break;
}
}
}
return dp[target][n];
}
};
