给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路：
可以看成每个元素是加上还是减去，标准的01背包问题。
dp[i][j]表示前i个物品，结果恰好是j的所有可能数目。dp[i][j]的构成是：
dp[i-1][j-num[i]],表示加上第i个元素。
dp[i-1][j+num[i]],表示减去第i个元素。
dp[i][j]+=(dp[i-1][j-num[i]]+dp[i-1][j+num[i]]).
注意：本题是存在前面全部是减去一个数的情况，因此j从逻辑上来说可能是负的，但数组的下标只能从0开始，因此需要将逻辑上的（-sum，+sum）转移到实际数组下标（0，2*sum）。则此时要找target就是j=sum+target。
初始化：
i=0时，仅有和为0有一种可能，则dp[0][sum]=1，j=0时，仅有i=n才有一种情况（即全都取负数）。其余位置全是0.
特殊情况：
target可能存在过大或者过小的情况，因为最后要返回的是dp[n][target+sum],但数组实际j取值范围是（0，2*sum），则若target<-sum或者target>sum,此时数组越界，因此需要单独讨论，但针对这两种情况，一定是取不到的，因此直接返回0就行。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n=nums.size();
int k=0;
for(auto e:nums)
{
k+=e;
}
if(k<target||-k>target)
return 0; //防止绝对不可能有任何组合结果为target导致数组越界
nums.insert(nums.begin(),0);
vector<vector<int>>dp(n+1,vector<int>(2*k+1,0));
dp[0][k]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=2*k;j++)
{
if(j-nums[i]>=0)
dp[i][j]+=dp[i-1][j-nums[i]];
if(j+nums[i]<=2*k)
dp[i][j]+=dp[i-1][j+nums[i]];
}
}
return dp[n][target+k];
}
};
