题目
给你一个整数数组 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
解题
方法一：动态规划
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = S
x = (S + sum) / 2
那么就可以转换为满背包问题，装满容量为X的背包就几种组合
dp[j] 就代表容量为j的背包有dp[j]种组合
填满容量为j - nums[i]的背包，有dp[j - nums[i]]种方法。
那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种方法。
因为每遍历到nums[i] ,都会多一组情况，因此dp[j]+=dp[j-nums[i]];
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum=accumulate(nums.begin(),nums.end(),0); if(abs(target)>sum) return 0;//如果nums中全是正的或者全是负的都不能满足target,就说明不存在 if((sum+target)%2==1) return 0; int bagSize=(sum+target)/2; vector<int> dp(bagSize+1,0); dp[0]=1; for(int i=0;i<nums.size();i++){ for(int j=bagSize;j>=nums[i];j--){ dp[j]+=dp[j-nums[i]]; } } return dp[bagSize]; } };
java
class Solution { public int findTargetSumWays(int[] nums, int target) { int sum=0; for(int num:nums) sum+=num; if(Math.abs(target)>sum) return 0; if((sum+target)%2!=0) return 0; int bagSize=(sum+target)/2; int[] dp=new int[bagSize+1]; dp[0]=1; for(int i=0;i<nums.length;i++){ for(int j=bagSize;j>=nums[i];j--){ dp[j]+=dp[j-nums[i]]; } } return dp[bagSize]; } }
