416. 分割等和子集

二维数组

class Solution {
    public boolean canPartition(int[] nums) {
        int size = nums.length;
        int sum = 0;
        for(int i : nums) {
            sum += i;
        }
        if( (sum & 1 ) != 0) return false;
        int target = sum >> 1;
        int[][] dp = new int[size][target + 1];
        for(int j = nums[0]; j <= target; j++ ) {
            dp[0][j] = nums[0];
        }
        for(int i = 1; i < size; i++ ) {
            for(int j = 0; j <= target; j++) {
                if(j < nums[i] ) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }
            }
        }
        return dp[size - 1][target] == target;
    }
}

滚动数组

class Solution {
    public boolean canPartition(int[] nums) {
        int size = nums.length;
        int sum = 0;
        for(int i : nums ) {
            sum += i;
        }
        if( (sum & 1) != 0) return false;
        sum /= 2;
        int dp[] = new int[sum + 1];
        for(int i = 0; i < size; i++ ) {
            for(int j = sum; j >= nums[i]; j-- ) {
                dp[j] = Math.max(dp[j],dp[j - nums[i] ] + nums[i] );
            }
        }
        return dp[sum] == sum;
    }
}