组合总和Ⅳ
题目要求
解题思路
来自[负雪明烛]
题目有个明显的提示:求组合的个数,而不是每个组合。如果是要求出每个组合,那么必须使用回溯法,保存所有路径。但是如果是组合个数,一般都应该想到[动态规划]的解法。
直接写出[动态规划]的解法,是有一定难度的。不妨先写出[记忆化递归],然后进行修改[动态规划]。
方法一:递归
要求构成target
有多少种组合方法,这里的变量应该是target
,所以,令函数dp(x)
表示从nums
中挑选数字可以构成x的方法数(递归最基本的就是理解这个定义!)。最终返回的应该是dp(target)
对于题目输入nums=[1,2,3]
,target =4的时候:要求有多少种方法能够组成4,即要求dp[4]
。思考过程如下:
我们遍历nums
,判断如果构成target
的时候,选择了nums[i]
,那么剩余的target-nums[i]
仍在nums
中选择的话,会有多少种方法。
于是一步一步出现了递归。这就是将大问题拆成小问题,然后发现小问题恰好可以用同样的函数解决,这就是递归思想。递归是一种思想与现象,绝不是为了递归而递归。
那么递归终止条件是什么呢?也就是说最基础的case应该直接返回什么结果?
- 如果给出的数字都是正整数,因此如果当要求的
target<0
的时候,无论如何都无法从数组中挑选元素构成,所以应该返回0; - 当要求的
target==0
的时候,需要return 1
。为什么?因为我们注意题目给出的输入target
一定是大于0的,如果在递归的时候target==0
,说明在for
循环中的target-num
得到了0,表示nums
数组中乔安后有一个数字等于target
。所以需要返回1。
会超时。
时间复杂度: O ( N t r a g e t ) O(N^{traget}) O(Ntraget),N是nums的长度,每次递归需要计算N次,递归深度最多target。
空间复杂度: O ( t a r g e t ) O(target) O(target)
方法二:记忆化递归
上面递归方法会超时,是因为有重复计算,比如计算dp(4)
的时候,计算了dp(2)
,而计算dp(3)
的时候又再次计算了dp(2)
。如果我们在递归的过程中,把已经计算了的结果放在数组、字典中保存,那么下次需要再计算相同的值的时候,直接从数组/字典中调用相同的计算结果,就能省下很多计算。
下面的代码演示了如何使用[记忆化递归]。定义了一个dp
数组,保存已经计算量的每个dp(x)
。dp
数组的每个位置初始化为-1,表示还没计算过。在递归函数刚开始的时候,不仅要判断target
是否<0
,还要判断当前计算的target
是否计算过(即dp[target] !=-1
)。只有在没计算过的情况下,才执行递归。并且在执行递归之后,需要把当前target
的计算结果保存到dp
数组中。
代码:
class Solution(object):
def combinationSum4(self, nums, target):
self.dp = [-1] * (target + 1)
self.dp[0] = 1
return self.dfs(nums, target)
def dfs(self, nums, target):
if target < 0: return 0
if self.dp[target] != -1:
return self.dp[target]
res = 0
for num in nums:
res += self.dfs(nums, target - num)
self.dp[target] = res
return res
复杂度分析
时间复杂度:
O
(
N
∗
t
a
r
g
e
t
)
O(N * target)
O(N∗target)
空间复杂度:
O
(
t
a
r
g
e
t
)
O(target)
O(target)
方法三:动态规划
理解了[记忆化递归]之后,离写出动态规划只有一步之遥。递归是自顶向下的计算方式(大问题-》小问题),而动态规划是自底向上的计算方式(小问题-》大问题)
动态规划也同样地定义dp
数组,dp[i]
表示从nums
中抽取元素组成target
的方案数。dp
数组的长度是target+1
。其中dp[0]
表示从数组中抽取任何元素组成0的方案数,根据我们在递归时的分析,我们需要知道令dp[0] = 1
。其他位置的dp[i]
需要初始化为0,表示我们还没有计算过这个位置,默认的方案数为0。
想要计算得到target
,需要把dp[1~target]
的各个元素都计算出来。每个位置的计算都是为了后面的计算做准备。
代码:
class Solution(object):
def combinationSum4(self, nums, target):
dp = [0] * (target + 1)
dp[0] = 1
res = 0
for i in range(target + 1):
for num in nums:
if i >= num:
dp[i] += dp[i - num]
return dp[target]
复杂度分析:
时间复杂度:
O
(
N
∗
t
a
r
g
e
t
)
O(N * target)
O(N∗target)
空间复杂度:
O
(
t
a
r
g
e
t
)
O(target)
O(target)