java刷题分割等和子集 动态规划

分割等和子集
转换成 0 1 背包

class Solution {
    public boolean canPartition(int[] nums) {
        //转化成 0 1 背包问题
        //dp[i] 为 容量为i 最大可以凑成i的子集总和
        //dp[i] = max(dp[i],dp[i-num[i]]+num[i])
        int len = nums.length;
        int sum  =0;

        for(int i =0; i
            sum += nums[i];
        }
        if(sum % 2 == 1) return false;

        int target = sum/2;


        int[] dp  = new int[10001];
        for(int i = 0 ;i < len; i++){
            for(int j = target; j >= nums[i];j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[target] == target) return true;
        return false;
    }
}