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

最后提交：