leetcode-分割等和子集

本题涉及到的是01背包问题，我将从两种解决背包问题的思路写出题解

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

乍眼一看可能看不出来和背包问题的联系，但是仔细想想，就是把nums的和分成一半，把一半当成背包，装nums里面的值，相等了另一半自然相等，既然如此首先这个nums的和就要满足是个偶数才能做到分割均匀，所以第一个判断就出炉了

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }

 判断完就开始准备对背包问题进行分析了

首先就是dp数组，这里dp[i][j]代表的就是从0-i这些元素里面取，j容量的背包能存的最大值

接下来就是递推公式：背包问题最重要的点就是能不能放得下，如果当前我们需要的值是j，j-nums【i-1】就是剩余的空间，如果放不下了就只能把刚才的值塞进了，如果还能放下，那就比较一下是刚才的值大还是当前值nums【i-1】加上剩余空间位置的最大值

 dp[i][j] = Math.max(dp[i - 1][j], nums[i-1] + dp[i - 1][j - nums[i-1]]);

最后就判断一下是否等于目标值就行。

因为我这里数组大小都加了1，所以不需要特意的初始化，直接都是0就行。

他的遍历顺序是从前往后的，因为我当前值是需要知道之前的值还有除了当前元素的最大空间，也就是想要得到当前值是需要上和左上方的值的！

上代码

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int m = nums.length;
        sum = sum / 2;
        int[][] dp = new int[m+1][sum+1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j - nums[i - 1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], nums[i-1] + dp[i - 1][j - nums[i-1]]);
                }
            }

        }
        return dp[m][sum] == sum;
    }
}

第二种方式就是 给他降维，变成一维数组

这个时候dp数组就表示放进物品后，背的最⼤重量为dp[j]，如果等于目标值了就说明装满了，而使用一维数组的时候物品遍历要放在外层，内层放的是背包，要倒序遍历

每到第i层，dp【i，nums【i】】是装不下当前物品的，所以不需要更新，从后往前遍历是因为dp需要比较当前值和nums值和剩余空间，如果从前往后，那么后面的值要依赖前面的值，所以可能会出现使用多次的情况

总结两点就是

1. 从大到小遍历：确保在更新 dp[j] 时，dp[j - nums[i]] 是在当前物品之前的状态，避免重复使用物品。

2. j >= nums[i] 的条件：只有当背包容量 j 大于或等于当前物品的重量 nums[i] 时，才可能将该物品放入背包，否则不需要更新 dp[j]

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

            }
        }
        return dp[target] == target;
    }
}