leetcode377 -- Combination Sum IV

leetcode377 -- Combination Sum IV

题目

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

这个题目比之前的三道又玩了花样,这次不仅元素可以重复用,而且(1,1,2)这样的竟然算了3次。 不过这个题的解法却比之前的几道都要简单一些,只要想到了办法

用DP来做,用dp[i]代表当target=i的时候解的个数,则显然dp[1]=1,然后我们将i从1遍历到target, 然后对于每一个i,我们要看他和nums中的每个数中的关系,如果i要比nums中的a要大或者相等,那么dp[i] += dp[i-a] 因为当前的target可以更新成i-a 从而转化成为了子问题,所以这样下去最终返回dp[-1]即可。

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0]*(target+1)
        dp[0] = 1
        
        for i in range(1, target+1):
            for a in nums:
                if i>=a:
                    dp[i] += dp[i-a]
        return dp[-1]

备注

但是其实我交不是太理解为什么dp[0]=1, 难道当target为0的时候必须有一个结果吗,是空集.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦