给你一个整数数组 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
解题思路
问题转化
这道题是要我们求一个 target，而整个表达式中是由正数和负数构成的，如果说我们又得照顾正数又得照顾负数问题，那么这道题就需要多个状态来表示啦，其实我们是可以通过简单的数学方程式来简化问题的，如下所示：
那么既然正数部分总和 a 是能直接得到的，那么我们直接转化为 求选择数组中元素和为 a 的这些数，一共有多少种选法！
这不就转化为 01背包 问题了吗，对不对！每个元素都是选和不选两种情况，并且背包的空间大小其实就是 a。
状态表示
根据 ”经验 + 题目要求“，设定状态表示为：dp[i][j] 表示在前 i 个元素中选择，总元素和正好等于背包容量 j，此时一共有多少种选法！
状态转移方程
其实背包问题的状态转移方程大体思路都是一样的，下图贴出来的是上一道题的 【分割等和子集】的图，可以发现只是在这个图种多了那项蓝色的提示，就是不需要加一或者加 nums[i] 因为状态表示的是一共有多少种选法，如果选择了该元素后成立，则表示这是一种成立的选法，但是只是前面选法变长罢了，并不会让选法加一！
而其它都是一模一样的，没错，这就是模板题的好处，但是细节也要小心~！
💥初始化
初始化就和之前不太一样了！
第一行表示没有元素可选，所以要凑成元素和为 j ，只有当背包空间为 0 的时候才能做到，因此 第一行仅需初始化第一个元素 dp[0][0] = 1。
第一列表示背包空间为 0，而题目说 nums[i] 是介于 [0, 1000] 的，也就是说 nums[i] 可能为 0，此时 dp[i][0] 既可能是 0，也可能是 1，那我们就得去遍历一遍判断一下每个位置然后初始化第一列。但是其实不需要，因为我们完全可以在后面填表的时候去完成这个工作，它所要做的是和填表时候要做的任务是一模一样的！所以我们压根不必去初始化第一列，只需要初始化为 0 即可！
遍历顺序
根据「状态转移方程」，我们需要「从上往下」填写每一行，每一行的顺序是「无所谓的」。
返回值
根据状态表示，返回 dp[n][a]。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 转换问题：
// 变成求数组中多少个数加起来等于a，其中a = (target + sum)/2，这是通过简单的方程组解出来的，具体参考笔记
// 此时a就相当于是背包空间
int sum = 0;
for(auto e : nums)
sum += e;
int a = (target + sum) / 2;
// 处理错误情况 -- 正数部分的和小于0，或者sum+target不是偶数
if(a < 0 || (target + sum) % 2 == 1)
return false;
// 创建dp表，dp[i][j]表示从前i个元素中选择，总元素和不超过j即不超过当前背包空间，此时的总选法数量
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(a + 1, 0));
// 初始化第一个元素为1即可
dp[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
// 注意下面j要从0开始遍历，因为背包空间为0时候有不同情况，一起在填表时候处理
for(int j = 0; j <= a; ++j)
{
// 如果不选nums[i]，则只需要加上前i-1个元素中选择的元素和等于j的总选法
dp[i][j] = dp[i - 1][j];
// 如果选nums[i]，则要判断是否会超过j即超过背包空间，超过的话则是没有意义的
// 注意下标映射关系
if(j >= nums[i - 1])
dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
return dp[n][a];
}
};优化
所有的「背包问题」，都可以进行空间上的优化。
对于 01背包 类型的，我们的优化策略是：
- 删掉第一维
- 修改第二层循环的遍历顺序即可
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 转换问题：
// 变成求数组中多少个数加起来等于a，其中a = (target + sum)/2，这是通过简单的方程组解出来的，具体参考笔记
// 此时a就相当于是背包空间
int sum = 0;
for(auto e : nums)
sum += e;
int a = (target + sum) / 2;
// 处理错误情况 -- 正数部分的和小于0，或者sum+target不是偶数
if(a < 0 || (target + sum) % 2 == 1)
return 0;
// 创建dp表
int n = nums.size();
vector<int> dp(a + 1);
// 初始化第一个元素为1即可
dp[0] = 1;
for(int i = 1; i <= n; ++i)
{
// 修改遍历j的顺序，并且改变for循环的判断条件，提高效率!!!
// 注意下标映射关系
for(int j = a; j >= nums[i - 1]; --j)
dp[j] += dp[j - nums[i - 1]];
}
return dp[a];
}
};