dp专题10 目标和
本题链接：. - 力扣（LeetCode）
题目：
思路：
根据这道题，可以通过暴力的方法进行取 + 号或者 - 号 两个操作，通过当刚好得到 target 的时候 答案 +1，但是通过长度是 20 ，操作状态为 2个，随后的回溯暴力递归，最坏的情况时间复杂度大约是 20^20^2 ,肯定会TLE了。
这时候就用到了动态规划dp，这里我们可以知道有两个操作 + -，我们分成两个子集，一些放正号子集 left，另一些放负号子集 righ。
最后得到 ： left + righ = sum 其中 sum 为整个 nums 数组的总和
然后将两个子集合并： left - righ = target
根据这两个式子我们可以推导出 left = (sum + target) / 2
这时候我们又可以将其看作为 背包问题了，根据题目意思要求的是能够凑成 target的方法有多少种，相当于背包问题中能够刚好装满给背包容量的方案数是多少一样的。
只是这里需要计算背包容量 v 为 left
代码详解如下：
inline int findTargetSumWays(vector<int>& nums, int target)
{int sum = 0; // 计算 nums 数组的总和for(int &i:nums) sum += i;// 分成两个子集， 一个是正号的子集 left , 一个是 负号的子集 righ// left + righ = sum// left - righ = target// left = (sum + target) / 2// 令 left 作为 背包容量，问刚好凑够 left 的子集有多少种方法// 其中 当 (sum + target) 不能被 2 整除 或者 当全部为 +号 或者 -号 的sum 小于 target，说明根本凑不齐int v = (sum + target) / 2;if(v * 2 != (sum + target) || abs(target) > sum) return 0;// dp[i] 中 i 含义为 ： 装满 容量 i dp[i] 含义为 装满 容量 i 的方法有多少种 int n = nums.size();vector<int>dp(n + 1000,0);/* 递推公式： dp[i - num[i]] = dp[i] 即： 有 dp[target - num[i]]种方法 凑成 dp[target] 假设 num[i] = i target = 5即： 1 dp[4] 种方法凑成 dp[5] 2 dp[3] 种方法凑成 dp[5]3 dp[2] 种方法凑成 dp[5]4 dp[1] 种方法凑成 dp[5]5 dp[0] 种方法凑成 dp[5]最后 dp[5] 中方法总共有： dp[0] + dp[1] + dp[2] + dp[3] + dp[4]最后公式为 dp[i] += dp[i - nums[i]]*/// dp 初始化， 0 凑成 0 的方法只有一种dp[0] = 1;for(int i = 0;i < n;++i){for(int j = v;j >= nums[i];--j){dp[j] += dp[j - nums[i]];}}return dp[v];
}