力扣 分割等和子集

动态规划，背包，前缀和。

题目

把这个数组分成两个数组，使其元素和相等，那这两个元素和相加一定是个偶数，即整个数组的前缀和一定是偶数，然后再分成一半即要找的目标值了。接着，就是遍历dp了，这道题的dp维护的遍历顺序跟01背包有点像，外循环是每一个数即每一个物品，内循环比较每一个数即背包的容量能不能装下这些物品，然后是从后往前遍历，防止状态先更新，因为当前需要的是上一个i，也是上一个物品，假如从前往后遍历，就会导致状态受到当前物品的影响先做更新比较时会不同。

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 == 1) {
            return false;
        }
        int target = sum / 2;//分割成一半，定为所求的元素和

      //看看这个数组中能不能找到凑成这个元素和
        boolean[] dp = new boolean[target + 1];
        Arrays.fill(dp, false);
        dp[0] = true;
     
     //倒叙遍历，跟01背包类似，为了不让dp[j - nums[i]状态先更新，应当来自上一个物品
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= nums[i]; j--) {
                if (dp[j - nums[i]]) {
                    dp[j] = true;
                }
            }
        }

        return dp[target];
    }
}

学会同类型题的迁移。