5. 目标和（LeetCode-494）
题目
给你一个整数数组 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
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
思路
怎么套？
分成两堆， l e f t − r i g h t = t a r g e t
又因为 l e f t + r i g h t = s u m
所以 l e f t = ( s u m + t a r g e t )/ 2
这和以前遇到的题目 不一样
先前：容量为 i 的背包，最多能装多少？
这次：填满容量为 i 的背包，有多少种方法？
五部曲
数组定义
dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法
递推公式
分两种情况，一种是不包含当前物品的方法数量，另一种是包含当前物品的方法数量。我们要求的就是二者 之和。为了方便，直接使用一维数组展示：
d p [ j ] = d p [ j ] + d p [ j − n u m s [ i ] ]
数组初始化
如果是二维数组，也就是要初始化第一行，即只有物品零的情况，可以想见，填满背包容量为零的方法有一种，就是不装东西。但填满不为零的背包的方法却为零，除非物品重量等于背包容量。所以在一维数组中初始化应该是 dp[0]=1 其他为0
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
代码展示
class Solution { public: int findTargetSumWays(vector<int> &nums, int target) { int sum = accumulate(nums.begin(), nums.end(), 0); if ((sum < target) || ((sum + target) % 2) || ((sum + target) < 0)) { return 0; } int left = (sum + target) / 2; vector<int> dp(left + 1); dp[0] = 1; for (int i = 0; i < nums.size(); i++) { for (int j = left; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } return dp[left]; } };
