Leetcode 416 分割等和子集
解法
背包问题的true和false,两个等和的子集,实际上就是何为总和的一半的子集,dp[i][j]的状态转移方程就可以解决了。
压缩空间的问题,对于target这一列,要倒着走,因为正着走会覆盖
代码
class Solution { public boolean canPartition(int[] nums) { /*int sum=0; for(int num:nums) { sum+=num; } if(sum%2==1) return false; int target=sum/2; boolean[][] dp=new boolean[nums.length][target+1]; for(int i=0;i<nums.length;i++) { dp[i][0]=true; } if(nums[0]<=target) dp[0][nums[0]]=true; for(int i=1;i<nums.length;i++) for(int j=0;j<=target;j++) { dp[i][j]=dp[i-1][j]; if(j-nums[i]>=0&&!dp[i][j]) { dp[i][j]=dp[i-1][j-nums[i]]; } } return dp[nums.length-1][target];*/ int sum=0; for(int num:nums) { sum+=num; } if(sum%2==1) return false; int target=sum/2; boolean[] dp=new boolean[target+1]; dp[0]=true; if(target>=nums[0]) dp[nums[0]]=true; for(int i=1;i<nums.length;i++) for(int j=target;j>=0;j--) { if(j-nums[i]>=0&&!dp[j]) { dp[j]=dp[j-nums[i]]; } } return dp[target]; } }
代码总结 文章被收录于专栏
典型的代码,以及自己的想法