154、【动态规划】leetcode ——494. 目标和：回溯法+动态规划（C++版本）

题目描述

原题链接：494. 目标和

解题思路

（1）回溯法

本题的特点是nums中每个元素只能使用一次，分别试探加上nums[index]和减去nums[index]，然后递归的遍历下一个元素index + 1。

class Solution {
public:int res = 0;void backtracking(vector<int>& nums, int target, int index) {if(index == nums.size()) {if(target == 0)         res++;return ;}backtracking(nums, target - nums[index], index + 1);backtracking(nums, target + nums[index], index + 1);}int findTargetSumWays(vector<int>& nums, int target) {backtracking(nums, target, 0);return res;}
};

（2）动态规划

本题中的数都为非负数，目标要求是选取组成正数的数与负数的数，让其和为target，因此我们可以将这个题中的数划分为两个集合，一个是要组成正数的集合，设容量为pos，一个是要组成负数的集合，设容量为neg。

由题中要求可得pos - neg = target，pos + neg = sum，联立两式，可得2 * pos = target + sum，因此我们就可以进行第一个判定，当target + sum不为偶数时，可知一定不能组合出target直接返回false即可。当为偶数时，我们要找到可以组成pos（pos = (target + sum) / 2）的组合。问题就可以转变为，当背包容量为pos时，选取nums里的数，有多少种组合方式可填满背包。

• 动态规划五步曲：

（1）dp[j]含义： 装满背包容量为j的方式个数。

（2）递推公式： dp[j] += dp[j - nums[i]]，装入nums[i]之前，容量为j - nums[i]时的方式个数dp[j - nums[i]]，再加上装入nums[i]之后，容量为j时之前的方式个数dp[j]，进而得到背包容量为j时，总的方式个数。

（3）dp数组初始化： dp[0] = 1，容量为0时，仅有一种方式可以成立，即选择数字0。

（4）遍历顺序： 先物品、再背包，内层按从大到小遍历的滚动数组。

（5）举例：

输入： nums: [1, 1, 1, 1, 1], S: 3
此时，正数最大为4，里面只有1，因此dp[j]长度为4。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sumNums = 0;for(int i = 0; i < nums.size(); i++)                    sumNums += nums[i];// target超过总和或者不满足pos为偶数的情况，直接返回0if(abs(target) > sumNums || (sumNums + target) % 2 != 0)     return 0;int dp[10001] = {0};dp[0] = 1;int pos = (sumNums + target) / 2;for(int i = 0; i < nums.size(); i++) {for(int j = pos; j >= nums[i]; j--) {// 组合情况要累计dp[j] += dp[j - nums[i]];}}return dp[pos];}
};

参考文章：494. 目标和、目标和、目标和（详细C++代码动态规划详细思路分析）