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];
}

最后提交：