LeetCode 494.目标和

1.题目：

https://leetcode.cn/problems/target-sum/description/

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

2.代码：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0; 
        for(int i:nums){
            sum+=i;
        }
        if(target<0 && sum<-target) return 0;//就是sum小于target的绝对值就返回0
        if((target+sum)%2 != 0) return 0;//当正数的个数的两倍不是偶数的时候，那么就不成立
        int left=(target+sum)/2;//这里的left表示的是正数的个数
        if(left<0) left=-left;//当left是负数的时候，把它全变成正
        int[] dp = new int[left+1];
        dp[0]=1;//初始化，表示一种方法，注意这里的的1表示的是方法
        for(int i=0;i<nums.length; i++){
            for(int j=left; j>=nums[i]; j--){
                dp[j]+=dp[j-nums[i]];//一个全新的不同于普通01背包的递推公式
            }
        }
        return dp[left];
    }
}

注意这里有好几种返回0的条件

推导：left+right=sum; left-right=target; right=sum-left; 

==>left=(target+sum)/2;

注意这里的递推公式，其实可以理解为每一个阶段的方法的累加，跟楼梯那个类似

例如：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]] 累加起来。