目标和（DP）
给你一个非负整数数组 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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
DP：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int total = 0;
for(int n : nums){
total += n;
}
if((total + target) % 2 != 0 || total < abs(target)){
return 0;
}
int sub = (total + target) / 2;
vector<int> dp(sub + 1, 0);
dp[0] = 1;
for(int n : nums){
for(int j = sub; j >= n; j--){
dp[j] += dp[j - n];
}
}
return dp[sub];
}
};(total + target) % 2 != 0：
如果 total + target 是奇数，那么无法将它分割成两部分，返回 0。
将 nums 划分为两个子集：一个子集 P 代表带正号的部分。另一个子集 N 代表带负号的部分。
根据题目要求，这两个子集满足：
- P − N=target
- P + N = sum(nums)
通过这两个方程，我们可以推导出 P 的值：
P=(sum(nums) + target) / 2
为了确保 P 是一个整数，(sum(nums) + target) 必须是偶数。如果 (sum(nums) + target) 是奇数，那么 P 就会是一个小数，在这种情况下，问题无解，直接返回 0。
total < abs(target)：
如果 total 小于 target 的绝对值，则无法通过 + 和 - 来组合出 target，所以直接返回 0。
这就变成了一个子集和问题：计算所有可以构成和为 sub 的子集数目。
定义dp[i] 表示可以组成和为 i 的子集数目。
初始时，dp[0] = 1，表示可以通过一个空集来组成和为 0 的子集。所有其他 dp[i]（对于 i > 0）都为 0，因为还没有计算任何子集。
为什么从 sub 开始倒序遍历？
- 为了避免当前的元素
n被重复使用。假设我们正在处理元素n并且当前正在更新dp[j]，如果我们从dp[sub]开始遍历并往下计算，就可以确保每次计算时，dp[j - n]只会使用上一轮的值。 - 如果我们从小到大遍历，可能会在同一轮循环中多次使用同一个元素
n，这会导致错误的计算。
dp[j] += dp[j - n] 的含义：
dp[j - n]代表当前元素n加入之前，可以组成和为j - n的子集数量。- 加上
n后，和变为j，因此可以通过将dp[j - n]加到dp[j]上，来表示有多少个子集和为j。 - 换句话说，
dp[j]就是之前可以组成和为j - n的子集数目与当前元素n组合后组成和为j的子集数目的和。
举个例子：
nums = [1, 2, 3]， sub = 4，那么 dp 数组初始化为：
dp = [1, 0, 0, 0, 0]
第一次循环，n = 1：
dp[4] += dp[4 - 1] = dp[3] → dp[4] = 0
dp[3] += dp[3 - 1] = dp[2] → dp[3] = 0
dp[2] += dp[2 - 1] = dp[1] → dp[2] = 0
dp[1] += dp[1 - 1] = dp[0] → dp[1] = 1
第二次循环，n = 2：
dp[4] += dp[4 - 2] = dp[2] → dp[4] = 0
dp[3] += dp[3 - 2] = dp[1] → dp[3] = 1
dp[2] += dp[2 - 2] = dp[0] → dp[2] = 1
第三次循环，n = 3：
dp[4] += dp[4 - 3] = dp[1] → dp[4] = 1
dp[3] += dp[3 - 3] = dp[0] → dp[3] = 2
最后：
dp = [1, 1, 1, 2, 1] ， dp[sub] = dp[4] = 1
DFS：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
return dfs(nums, target, 0, 0);
}
int dfs(vector<int>& nums, int target, int i, int sum){
if(i == nums.size()){
return sum == target ? 1 : 0;
}
int a = dfs(nums, target, i + 1, sum + nums[i]);
int b = dfs(nums, target, i + 1, sum - nums[i]);
return a + b;
}
};