LeetCode-494. 目标和-蒲公英云

题目来源
494. 目标和

思路

01背包问题是选或者不选，但本题是必须选，是选+还是选-。先将本问题转换为01背包问题。假设所有符号为+的元素和为x，符号为-的元素和的绝对值是y。我们想要的 S = 正数和 - 负数和 = x - y 而已知x与y的和是数组总和：x + y = sum 可以求出 x = (S + sum) / 2 = target 也就是我们要从nums数组里选出几个数，令其和为target 于是就转化成了求容量为target的01背包问题 =>要装满容量为target的背包，有几种方案
特例判断如果S大于sum，不可能实现，返回0 如果x不是整数，也就是S + sum不是偶数，不可能实现，返回0

看的时候没看太明白，我再重新描述一遍，把数组里的所有数字分成两个部分，一部分的和为x，一部分的和为y。所以x+y就等于数组的总和sum。因为s<=sum的，所以我们要让一部分数字为负数，就让y为负数，所以x-y=s。我们的重点就转移到x上了，求数组里和为x的情况。（x=(sum+s)/2）

回溯法

class Solution {
    int ans = 0;
    public int findTargetSumWays(int[] nums, int target) {
        if(nums == null){
            return 0;
        }
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if((target+sum)%2 == 1){
            return 0;
        }
        int bagSize = (target+sum)/2;
        backTracking(nums,bagSize,0,0);
        return ans;
    }
    public void backTracking(int[] nums,int bagSize,int startIndex,int sum){
        if(sum == bagSize){
            ans += 1;
        }
        if(sum > bagSize){
            return;
        }
        for(int i =startIndex;i<nums.length;i++){
            sum += nums[i];
            backTracking(nums,bagSize,i+1,sum);
            sum -=nums[i];
        }
    }
}

在这里插入图片描述

做这个要注意一个问题，不能写return，可能之后还有0的情况，那么也是一种组合

if(sum == bagSize){
            ans += 1;
            return;
        }

在这里插入图片描述

动态规划

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        if(nums == null){
            return 0;
        }
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //target的绝对值已经大于sum
        if(Math.abs(target)>sum){
            return 0;
        }
        if((target+sum)%2 == 1){
            return 0;
        }
        int bagSize = (target+sum)/2;
        int[][] dp = new int[nums.length][bagSize+1];
        dp[0][0] = 1;
        for(int j = 0;j<=bagSize;j++){
            if(j == nums[0]){
                dp[0][j]++;
            }
        }
        for(int i = 1;i<nums.length;i++){
            for(int j = 0;j<=bagSize;j++){
                if(j<nums[i]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[nums.length-1][bagSize];
    }
}

在这里插入图片描述

动态规划(压缩)

1.确定dp数组以及下标的含义

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

2.确定递推公式

只要搞到nums[i]），凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，

已经有一个1（nums[i]）的话，有 dp[4]种方法凑成容量为5的背包。
已经有一个2（nums[i]）的话，有 dp[3]种方法凑成容量为5的背包。
已经有一个3（nums[i]）的话，有 dp[2]中方法凑成容量为5的背包
已经有一个4（nums[i]）的话，有 dp[1]中方法凑成容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法凑成容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。

dp[j] += dp[j - nums[i]]

dp[j] += dp[j - nums[i]]对这句组合数的理解： 1、如果不选第i个数（nums[i]）的话，则方法数为dp[j]； 2、如果选第i个数（nums[i]）的话，则方法数为dp[j - nums[i]]；所以方法总数为：dp[j] = dp[j] + dp[j - nums[i]]；（感觉这样拆开写比较容易理解）可以对比其他01背包问题：dp[j] = max(dp[j], dp[j - nums[i]])，这种问题即是从选i与不选i里，选取最大值。

3.dp数组如何初始化

如果数组[0] ，target = 0，那么 bagSize = (target + sum) / 2 = 0。 dp[0]也应该是1，也就是说给数组里的元素 0 前面无论放加法还是减法，都是 1 种方法。

如果是数组[0,0,0,0,0] target = 0 呢。
其实此时最终的dp[0] = 32，也就是这五个零子集的所有组合情况，但此dp[0]非彼dp[0]，dp[0]能算出32，其基础是因为dp[0] = 1 累加起来的。
dp[j]其他下标对应的数值也应该初始化为0，从递推公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来。

4.确定遍历顺序

nums放在外循环，target在内循环，且内循环倒序。

5.举例推导dp数组

输入：nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下：
在这里插入图片描述

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