494.目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

分析：这道题还是0-1背包问题，不同的是要求出方法有多少种，这个就要换一个递推公式了；
假设数组和为sum，目标值target，正数为left，负数为right，那么可以得到两个公式：
left+right=sum;
left-right=target;
其中sum，target是已知量，left,right是未知量，那么可以组成一个式子，消除掉一个未知量，即：
left-(sum-left)=target;
化简得：2left=sum+target；
好了，问题变了，变成了在数组中找到和为（sum-target）/2,一共有几种方法
对于求几种方法的0-1背包问题，递推公式为：
dp[j]+=dp[j-nums[i]]；
这道题还要考虑一下初值的问题，初值不能设为0，不然依靠初值递推均为0了，初值需要设置为1；

参考代码：
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int i:nums){
sum+=i;
}
if((sum+target)%2==1) return 0;
if(target>sum) return 0;
int bag = (sum+target)/2;
if(bag<0) bag=-bag;
int[] dp = new int[bag+1];
dp[0]=1;
for(int i=0;i for(int j=bag;j>=nums[i];j—){
dp[j]+=dp[j-nums[i]];
}
}
return dp[bag];
}