和为target问题汇总

• 和为target的问题，可以有很多种问题的形式的考察，当然，及时的总结与回顾有利于我们熟练掌握这些知识！

习题

377.组合总和 IV

377.组合总和 IV

• 思路分析：通过观察，由于nums数组里面的元素可以重复选择，并且没有数量限制，所以这个题目就是一个有len(nums)个选择的爬楼梯问题，所以我们就是使用爬楼梯问题模版进行解决
• 总体的时间复杂度是o(n*target)

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:# 动态规划的问题，nums[i]中为你每一步可以选择的步伐大小# 定义dp[i]表示到达i的方案数，那么就可以由先前的位置转移而来dp = [1]+[0]*targetfor i in range(1,target+1):cou = 0for j in nums:if i - j >= 0:cou += dp[i-j]dp[i] = coureturn dp[target]

494.目标和

494.目标和

• 思路分析：
• 这是一个子序列和为target的问题，需要定义dp[i][j]为前i个数字中，对应和为j的方案数，所以我们需要使用一个二重循环进行求解
• 当然这题就是需要转换一下

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# 类似于0-1背包问题，求解的是运算结果等于target的表达式的数目# 我们可以照常选择正数zheng，那么对应的负数就是sum(nums) - zheng# dp[i][j] 定义为前i个数字中，值为j的数目# dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]] ,计算nums[i]=0也没关系，+，-0算两个表达式# 那么dp数组怎么开这个target,原本的困惑，就是选了正数还要管这个target的范围# 由式子，选取正数的和为p,要减去的数字和为q,有p+q=s,p-q = target，就可以求解出p与q的值即可# 我们只要开的空间等于其中一个即可,也可以去一个绝对值都算上s = sum(nums) - abs(target)if s<0 or s%2 == 1:return 0m = s // 2n = len(nums)dp = [[0]*(m+1) for _ in range(n+1)]# 赋初值为1，不然后面算不了dp[0][0] = 1for i in range(n):for j in range(m+1):if j < nums[i]:dp[i+1][j] = dp[i][j]else:# dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]dp[i+1][j] = dp[i][j] + dp[i][j-nums[i]]return dp[n][m]