给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
> 动态规划
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 假设加法的总和为x，那么减法对应的总和就是sum - x。
// 所以我们要求的是 x - (sum - x) = target
// x = (target + sum) / 2
// 此时问题就转化为，装满容量为x的背包，有几种方法
int sum = 0;
int len = nums.size();
for(int i = 0; i < len; i++){
sum += nums[i];
}
if(sum < abs(target)) return 0;
int t = (sum + target) % 2;
if(t == 1) return 0;
else t = (sum + target) / 2;
vector<int> dp(t+1,0);
dp[0] = 1;
for(int i = 0; i < len; i++){
for(int j = t; j >= nums[i];j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[t];
}
};