pydata

Keep Looking, Don't Settle

leetcode 377. Combination Sum IV

377. Combination Sum IV

题目大意 给定一个整型数组,里面没有重复数字。求解所有可能的组合使得组合的和为给定的整数。

解题思路:使用dp(nums, target)表示所有的组合来得到目标值。那么对nums里的每一个num_i,dp(nums, target) = num_i X dp(nums, target - num_i)

所以可以使用记忆化递归的办法来求解。

1. 记忆化递归

class Solution(object):
    def combinationSum4(self, nums, target):
        self.f = [-1 for _ in range(target + 1)]
        self.f[0] = 1
        def dp(nums, target):
            if target < 0:
                return 0
            if self.f[target] != -1:
                return self.f[target]
            ans = 0
            for num in nums:
                ans += dp(nums, target - num)
            self.f[target] = ans
            return ans
        return dp(nums, target)

2. 递推/动态规划

class Solution(object):
    def combinationSum4(self, nums, target):
        f = [0 for _ in range(target + 1)]
        f[0] = 1
        for i in range(1, target + 1):
            for num in nums:
                if i - num >= 0:
                    f[i] += f[i - num]
        return f[target]