dp专题10 目标和

2024-01-08 17:31:45

本题链接:. - 力扣(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];
}

最后提交:

文章来源:https://blog.csdn.net/hacker_51/article/details/135460549
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。