力扣494-目标和（Java详细题解）

题目链接：494. 目标和 - 力扣（LeetCode）

前情提要：

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

最近刚学完01背包，所以现在的题解都是以01背包问题为基础再来写的。

如果大家不懂01背包的话，建议可以去学一学，01背包问题可以说是背包问题的基础。

如果大家感兴趣，我后期可以出一篇专门讲解01背包问题。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组 利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

这里下文统一使用一维dp数组。

题目思路:

该题刚入手，可能会让人很懵，那么多元素，我们如何选择给每个元素添加+号还是-号。

不急，dp类的题目就是要善于找规律，找到规律，核心思路就确定了。

我们设x为整个数组添加 + 的元素和，sum - x 就是设为 - 号的元素总和。

这里的元素和不涉及符号 就是数组中添加为+的元素的和。

x-(sum - x) = tagert。

x =(tagert + sum) / 2。

得出这个结论后，我们的思路是不是就清晰许多。

数组中添加为+的元素和 = 目标整数和整个数组元素和的一半。

本题要求数组用+和-号凑成target有多少种方法。

此时问题就转化为，我们装满这个x有多少种方法。

抽象出来就是x当做背包容量，nums[i]就是物品。

当我们数组中添加+的整数确定后，那添加为-号整数也就确定下来了。

大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了，例如sum是5，target是2 的话其实就是无解的，所以：

if ((target + sum) % 2 == 1) return 0; // 此时没有方案

同时如果target 的绝对值已经大于sum，那么也是没有方案的。

if (Math.abs(target) > sum) return 0; // 此时没有方案

接下来我们用dp五部曲来系统分析一下。

1.确定dp数组和i下标的含义。

dp[j] 就是装满j时方法的数量。

2.确定递推公式。

每个物品只有选和不选俩种状态。不选的状态就是dp[j]，因为没有选，背包容量不会减少。此时就是不选当前物品时能装满的方法的数量。

选的状态就是dp[j - nums[i]]，因为此时我们选择了该物品，我们就要求在装入该物品之前的装满背包的方法种类的数量然后再放入该物品。

放入该物品的状态就是dp[j - nums[i]]。

肯定有人疑问为啥不加1呢? 此时我们是选择装入该物品，首先我们得知道装入该物品之前装满的方法数量，那么加上该物品其实并不会让该方法数量加一，已经选择了该物品，所以方法数量就是dp[j - nums[i]]。

举个例子。比如我们选择了当前物品1，此时背包容量为4。

此时选择的状态就是dp[j - 1] = dp[3]。

就是装入该物品之前装满的方法数量，而此时我们其实已经选择了装入了当前物品 ,也就是说此时装满背包容量为4选择当前物品的状态就是dp[3]。

因为这个一种方法，而不是物品的数量，如果是数量，那么加入该物品肯定是要加1，但是这是一种选择方法，我已经选择了，所以就不会加1。

所以我们的递推公式就能推出，因为每个物品只有选和不选俩个状态，所以dp[j] = dp[j] + dp[j - nums[i]]；

也就是当前背包容量为j的装满的方法数量，等于他不选择当前物品和选择当前物品的总方法数量。

所以再精简点就是dp[j] += dp[j - nums[i]]；

3.dp初始化。

这里我们只用初始化dp[0]即可，其他的非0下标都可以由dp[0]来推出。

那么dp[0]初始化为多少呢，dp[0]其实就是当背包容量为0时，所能装满的方法数量。

背包容量为0，我们是不是能想到此时背包就是满的，因为他不能放东西嘛，所以此时对他来说也就是满的。

所以dp[0] = 1。

4.确定dp的遍历顺序。

该题与01背包的遍历顺序相同，物品从前往后遍历，背包容量从后往前遍历上为了保证每个物品只放入了一次。

5.如果没有ac打印dp数组 利于debug。

如果没有出现差错，我们就可以不用打印，因为我是写题解，所以我就不添加核心代码以外的代码，不然代码显的有些冗余。

举个例子。

最终代码：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //定义总和
        int sum = 0;
        for(int i = 0;i < nums.length;i ++)sum += nums[i];
        //如果target的绝对值大于sum，那么是没有方案的
        if (Math.abs(target) > sum) return 0;
        //如果(target+sum)除以2的余数不为0，也是没有方案的
        if ((target + sum) % 2 == 1) return 0;
        //定义背包容量
        int avg = (sum + target) / 2;
        //定义dp数组
        int[] dp = new int[avg + 1];
        //dp数组初始化
        dp[0] = 1;
        //遍历dp数组
        for(int i = 0;i < nums.length;i ++){
            for(int j = avg; j >= nums[i];j --){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[avg];
    }
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！