5 动态规划解分割等和子串

来源：LeetCode第416题

难度：中等

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

分析：相当于从nums数组中选取一些元素，使得他们的和为总和/2

递归求解：

public Boolean getSum(int []nums)
{
int sum=0;
for(int number:nums)
{
sum+=number;
}
if(sum%2!=0)
{return false;
​​​​​​​}
return GetSum(nums,sum/2,0)
}
public Boolean GetSum(int []nums,int sum,int index)
{
if(index>=nums.length)
{
if(sum==0)
{
return 1;
}else
{
return 0;
}
}

return GetSum(nums,sum-nums[index],index+1)||GetNum(nums,sum,index+1);
}

可以看做是一个背包问题dp[i][j]表示前i个字符是否能组成和为j的部分dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];

public Boolean getSum2(int[]nums)
{
int sum=0;
for(int number:nums)
{
sum+=number;
}
if(sum%2!=0)
{
return false;
}
Boolean dp[][]=new Boolean [nums.length][sum>>1];
if(nums[0]==0)
{
dp[0][0]=true;
}else{
dp[0][0]=false;
}
for(int i=1;i<nums.length;i++)
{
if(nums[i]==0)
{
dp[i][0]=true;
}else
{
dp[i][0]=dp[i-1][0];
}
}

for(int i=1;i<nums.length;i++)
{
for(int j=0;j<sum>>1;j++)
{
if(nums[i]<=j)
{
dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
}else
{
dp[i][j]=dp[i-1][j];
}

}
}
return dp[nums.length-1][num>>1];
}