Leetcode-416-分割等和子集

题目

image.png

题解

题解1

0-1背包问题

// 思路
// 总和必须是偶数吧
// 状态：总和容量，nums个数
// 动作：i选择或是不选择
// dp[i][j]意义：前i个数字，能不能总和为j
// dp[i][j] = dp[i-1][j-nums[i]] i选择，前i-1个数之和为j-nums[i], dp[i-1][j] i不选择
// base case dp[0][...]=false:前0个数（数字从1开始）能得到和为...,所以不可能
// dp[...][0] 前...个数，得到和为0，true？？？
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[n + 1][target + 1];
        // dp[0][...]=false,dp[...][0]=false
        for (int i = 0; i <= n; i++) {        // ???
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                if (nums[i-1] <= j) {      // 注意索引
                    dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];       // 选不了
                }
            }
        }
        return dp[n][target];
    }
}

题解2

状态压缩

class Solution {
    public boolean canPartition(int[] nums){
        int len = nums.length;
        if (len<=0) return false;
        int sum=0;
        for (int i=0; i<len;i++)
            sum += nums[i];
        if (sum%2!=0) return false;
        sum = sum/2;
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        // dp[nums[0]] = true;               // 如果nums=[100], nums[100, 2]....sum<nums[0]
        if (nums[0]<=sum){
            dp[nums[0]] = true;
        }else{
            return false;
        }
        for (int i=1; i<len; i++){
            for (int j=sum; j>=0; j--){
                if (j>=nums[i])
                    dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        return dp[sum];
    }

    // public boolean canPartition(int[] nums) {
    //     int len=nums.length;
    //     if (len<=0) return false;
    //     int sum=0;
    //     for (int i=0; i<len;i++)
    //         sum += nums[i];
    //     if (sum%2!=0) return false;
    //     sum = sum/2;
    //     boolean[][] dp = new boolean[len][sum+1];
    //     for (int i=0; i<len; i++){
    //         Arrays.fill(dp[i], false);
    //         dp[i][0] = true;
    //     }
    //     for (int j=0; j<=sum; j++){              // 
    //         if (j==nums[0]){
    //             dp[0][j] = true;
    //             break;
    //         }
    //     }
    //     for (int i=1; i<len; i++){              // i=1
    //         for (int j=1; j<=sum; j++){
    //             if (dp[i][j]) continue;
    //             // dp[i][j] = (i-1>=0?dp[i-1][j]:false);
    //             dp[i][j] = dp[i-1][j];
    //             if (j>=nums[i]){
    //                 // dp[i][j] = dp[i][j] || (i-1>=0?dp[i-1][j-nums[i]]:false);
    //                 dp[i][j] = dp[i][j] || dp[i-1][j-nums[i]];
    //             }
    //         }
    //     }
    //     return dp[len-1][sum];
    // }

    // public boolean canPartition(int[] nums) {
    //     int len = nums.length;
    //     if (len<=0) return false;
    //     int sum=0;
    //     for (int i=0; i<len;i++)
    //         sum += nums[i];
    //     if (sum%2!=0) return false;
    //     sum = sum/2;
    //     int[][] dp = new int[len][sum+1];
    //     for (int i=0; i<len;i++){
    //         Arrays.fill(dp[i], 0);
    //         dp[i][0] = 0;
    //     }
    //     for (int i=0; i<len; i++){
    //         for (int j=1; j<=sum; j++){
    //             //if (dp[i][j]!=-1) continue;
    //             dp[i][j] = (i-1>=0?dp[i-1][j]:0);
    //             if (j>=nums[i])
    //                 dp[i][j] = Math.max(dp[i][j], (i-1>=0?nums[i]+dp[i-1][sum-nums[i]]:0));
    //             if (dp[i][j]==sum) return true;
    //         }
    //     }
    //     return false;
    // }
}

参考

0-1背包问题
0-1背包问题的变种