leetcode416. 分割等和子集

题目链接
思路：动态规划（0、1b背包问题）
分析：这道题可以稍微变换一下，分割出来两个相同的和，那么这两个相同的和必定是全部累加的一半，也就是说，这个题目可以转换成，挑选出k个数，使得和为tar。
我们定义一个dp[i][j]：表示从[0,i]闭区间挑选一些数字(当然也可以一个也不挑)等于j的true/false
首先，dp[i][0]=true，也就是说，0到任何区间，一个都不挑选，等于0都可以成立
dp[0][nums[0]] = true，也就是说，挑选nums[0]为true
状态转移方程：

dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[j-nums[i-1]]]

代码：

class Solution {    public boolean canPartition(int[] nums) { int n = nums.length; if(n==1){     return false; } int sum = 0; int max = 0; for(int num : nums){     sum += num;     max = Math.max(max,num); } int tar = sum >> 1; if((sum&1)==1 || max > tar){     return false; } if(max == tar){     return true; } //dp[i][j] 表示从[0,i]区间内挑选出来一些数使得可以等于j boolean[][] dp = new boolean[n][tar+1]; for(int i = 0 ; i < n;i++){     dp[i][0] = true; } dp[0][nums[0]]  = true;  for(int i = 1; i < n;i++){     for(int t = 1; t <=tar; t++){  dp[i][t] = dp[i-1][t];  if(t>=nums[i]){      dp[i][t] |= dp[i-1][t-nums[i]];  }     } } return dp[n-1][tar];    }}