【LeetCode】494. 目标和(枚举，动规，背包三种方法，java实现）

题目

题解

方法一：枚举

我们可以使用递归，枚举出所有可能的情况。具体地，当我们处理到第 i 个数时，我们可以将它添加 + 或 -，递归地搜索这两种情况。当我们处理完所有的 N 个数时，我们计算出所有数的和，并判断是否等于 S。

public class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }
    public void calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S)
                count++;
        } else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

复杂度分析

时间复杂度： $O(2^N)$ ，其中 NN 是数组 nums 的长度。
空间复杂度：O(N)，为递归使用的栈空间大小。

方法二：01背包

1.把该问题转换成0-1背包问题，可惜我一上来就卡死在这里了，其实是很简单的数学关系，当时就是想不出，把评论区大佬的讲解贴在这吧：
QQ截图20200523185017.png

所以物品就相当于nums元素,P就是背包。选物品，就是把对应的数放进正子集P里，不选则不放，最终要求P的元素和，即背包容量，刚好等于(target + sum(nums)) / 2

2.接下来就是常见的求0-1背包方案数的问题，这里是恰好装满背包的方案数，看看背包九讲就会了
直接把状态转移方程贴这里：

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
  int sum=0;
        int len=nums.length;
        for (int n:nums)  sum+=n;
        int target;
        if(sum < Math.abs(S) || (sum+S)%2!=0) return 0;
        target=(sum+S)/2;
        int [] dp=new int[target+1];
        dp[0]=1;//表示从前0个物品中选取若干放入背包承重量为0的恰好装满的方案数
        for(int i=1;i<=len;i++){
            for(int j=target;j>=nums[i-1];j--){
                dp[j]=dp[j]+dp[j-nums[i-1]];
            }
        }
        return dp[target];
    }
}

方法三：动态规划

动态规划（背包问题）

虽然上述回溯法超时了，但是依旧给我提供了后续思路，我们仔细观察一下回溯法在这道题的解题框架：

//选择列表
for(int i = index; i<nums.length; i++){
    //选择做出+nums[i]
    ... ...
        
    //选择做出-nums[i]
    ... ...
}

上述框架叙述了这样一件事，在选择nums[i]这个数的时候，我们该选择+呢？还是选择-呢？还是两种都要算一起呢？写到这思路渐渐明朗起来。这就相当于在背包载重最大为j的情况下，对前i个物品进行选择。这样我们就转换成了背包问题了。

当然，这道题肯定是两种都要算一起，因为我们最后求的是和为目标数 S 的所有添加符号的方法数。

那状态转移方程就出来了。

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

解释：j+nums[i]和j-nums[i]表示对nums[i]可以执行加，还可以执行减，那么dp[i][j]的结果值就是加/减之后对应位置的和。

接下来需要明确base case，在本题中这也是关键的一步，很多小伙伴会卡在这里。在这之前我们需要明确状态与选择。对于本题来讲：

状态：即目标和（有范围）
选择：+或- nums数组中的元素

解释：例如，在示例nums = [1, 1, 1, 1, 1]中在非负整数数组的前提下，由于为是要选择+或者-，那么：

组成的最大和就是对所有元素全选+。sum = 5。
组成的最小和的是对所有元素全选-。sum = -5 。

说明我们的目标和S一定是 -5<= S <=5的，其范围长度length = sum*2 + 1。这样就确定下状态了。那我们的dp表就是:

因为整个状态的范围长度length = sum*2 + 1，而j是从0开始的，故其初始化的位置应为sum。由于状态转移方程为dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[i]].故dp表初始化应为：

if(nums[0] == 0) dp[0][sum] = 2;
else{
    dp[0][sum+nums[0]] = 1;
    dp[0][sum-nums[0]] = 1;
}

如果nums[0]==0的话，那么+0和-0都应该算作其操作，故if(nums[0] == 0) dp[0][sum] = 2;


class Solution{
    public int findTargetSumWays(int[] nums, int S){
        if(nums.length == 0) return 0;
        int sum = 0;
        for(int i = 0; i < nums.length; i++) sum += nums[i];
        if (Math.abs(S) > Math.abs(sum)) return 0;
        int[][] dp = new int[nums.length][sum*2+1];
        if(nums[0] == 0) dp[0][sum] = 2;
        else{
            dp[0][sum+nums[0]] = 1;
            dp[0][sum-nums[0]] = 1;
        }
        
        for(int i = 1; i<nums.length; i++){
            for(int j = 0; j<(sum*2+1);j++){
                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                int r = (j + nums[i]) < (sum*2+1) ? j + nums[i] : 0;
                dp[i][j] = dp[i-1][l] + dp[i-1][r];
            }
        }
        return dp[nums.length-1][sum+S];
    }
}