LC 动态规划-背包问题-416

方法1.
可以采用一个二维数组存放该数组中的数相加所能到达的每个数值，最后判断是否有target.

public boolean canPartition(int[] nums) {
    int len = nums.length;
    if(len == 1){
        return false;
    }
    if(len == 2){
        return nums[0] == nums[1];
    }
    int sum = 0;
    for(int num : nums){
        sum += num;
    }
    if(sum % 2 == 1){
        return false;
    }
    int target = sum/2;
    int[][] matrix = new int[nums.length][target + 1];
    matrix[0][nums[0]] = 1;
    for(int i = 1; i < nums.length; i++){
        int temp = i - 1;
        if(nums[i] < target + 1){
            matrix[i][nums[i]] = 1;
        }else{
            continue;
        }
        for(int j = 0; j < target + 1; j++){
            if(matrix[temp][j] == 1){
                matrix[i][j] = 1;
                if(j + nums[i] < target + 1){
                    matrix[i][j+nums[i]] = 1;
                }
            }
        }
    }

    return matrix[nums.length-1][target] == 1;
}

方法2
转换为背包问题

public boolean canPartition(int[] nums) {
    int len = nums.length;
    if(len == 1){
        return false;
    }
    if(len == 2){
        return nums[0] == nums[1];
    }
    int sum = 0;
    for(int num : nums){
        sum += num;
    }
    if(sum % 2 == 1){
        return false;
    }
    //target == 11
    //每个数肯定都小于等于target~
    int target = sum/2;
    int[] dp = new int[target + 1];
    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]);
        }
    }
    
    return dp[target] == target;
}

这个问题可以转化为将数组尽量分为大小相同的两组，然后进行操作就行了。

public int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for(int st : stones){
        sum += st;
    }
    int target = sum/2;
    int[] dp = new int[target + 1];
    for(int i = 0; i < stones.length; i++){
        for(int j = target; j >= stones[i]; j--){
            dp[j] =  Math.max(dp[j],dp[j-stones[i]] + stones[i]);
        }
    }

    return Math.abs((sum - dp[target]) - dp[target]);
}