组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。

示例:

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

所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意,顺序不同的序列被视作不同的组合。

因此输出为 7。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iv

根据题意:只要求求出组合的个数,所以我们可以用动态规划的方法来进行求解,如果是求具体的组合情况,则需要用回溯算法和组合总和一样的方法。
既然是动态规划,我们首先要求出的是它的状态方程。
画出图像逐一分析

377-1.png

以target的值为dp的范围(dp = [1, 0, 0, 0, 0]),只有每次 target = 0的时候结算,对于target <= 0的情况直接剪枝停止。
所以dp方程为:dp[i] = sum(dp[i - num] for num in nums if i >= num) ——> dp[4] = dp[3] + dp[2] + dp[1]
具体代码如下:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0 for _ in range(target + 1)] # 建立dp表
        dp[0] = 1  # 设空为 1 (满足target条件)
        for i in range(1, target + 1):
            for j in nums:
                if i - j >= 0:
                    dp[i] += dp[i - j]
        return dp[-1]
点赞

发表评论

Title - Artist
0:00