LeetCode494：目标和

题目链接：494. 目标和 - 力扣（LeetCode）

代码如下

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i];}if(abs(target) > sum)   return 0;if((target + sum) % 2 == 1) return 0;int bagsize = (target + sum) / 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];}
};

这个题目也可以这么理解，怎么把加法和减法做一个排列组合，主要是这个dp[j] = dp[j - nums[i]];这个是怎么推导出来的。如果我们选了物品1，那么就有dp[4]种方法凑成dp[5]，选择物品2的话，有dp[3]凑成dp[5],以此类推，那么dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0];这里的初始化还是有很大的学问的，这里需要把dp[0] = 1;