494. 目标和 Medium

给你一个非负整数数组 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

提示：

 ·1 <= nums.length <= 20

 ·0 <= nums[i] <= 1000

 ·0 <= sum(nums[i]) <= 1000

 ·-1000 <= target <= 1000

题目大意：在每个数可正可负的情况下计算所有数和为target的表达式数目。

分析：

（1）设所有数都是正数时的和为sum，添加负号的元素的绝对值和为tar，使(sum-tar)-tar=target，则tar=(sum-target)/2；

（2）由（1）可知，当(sum-target)%2==1或者sum-target<0时，不可能有和为target的表达式，返回0即可；否则在原数组中选取若干元素使其所选元素的绝对值和为tar即可满足表达式和为target，因此所求的表达式数目为从数组中选取若干元素使绝对值和为tar的方案数；

（3）为求从数组中选取若干元素使绝对值和为tar的方案数，可设二维数组dp，dp[i][j]表示从数组中前i个元素中选取若干元素使绝对值和为j的方案数。则当j<nums[i]时，dp[i][j]=dp[i-1][j]，当j>=nums[i]时，dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]。最终dp[nums.size()][tar]的值即为从数组中选择若干元素使绝对值和为tar的方案数，返回即可；

（4）由于dp数组每一行的元素只与上一行的元素有关，因此可对dp数组进行降维，则dp[k]表示遍历第i个元素时从前i-1个元素中选取若干元素使绝对值和为k的方案数。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int N=nums.size(),sum=0;for(int ele:nums) sum+=ele;int diff=sum-target,tar=diff/2;if(diff<0||diff%2) return 0;vector<int> dp(tar+1,0);dp[0]=1;for(int ele:nums){for(int k=tar;k>=ele;--k) dp[k]+=dp[k-ele];}return dp[tar];}
};