和为target问题汇总
文章目录
- 习题
- 377.组合总和 IV
- 和为
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]