算法第十一天-组合总和Ⅳ

2024-01-09 06:59:21

组合总和Ⅳ

题目要求

解题思路

来自[负雪明烛]
题目有个明显的提示:求组合的个数,而不是每个组合。如果是要求出每个组合,那么必须使用回溯法,保存所有路径。但是如果是组合个数,一般都应该想到[动态规划]的解法。
直接写出[动态规划]的解法,是有一定难度的。不妨先写出[记忆化递归],然后进行修改[动态规划]。

方法一:递归

要求构成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)

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