【每日一题】组合总和 Ⅳ

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

这题一开始还试图用之前递归的方法做，但发现这边需要考虑不同顺序。用动态规划递推来做会比较简洁。

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        dp = [0] * (target + 1) # dp[i]表示和为i的不同组合数，初始化为0
        dp[0] = 1 # 总和为0的组合方式只有一种，即空集
        
        for i in range(1, target + 1): 
            for num in nums:
                if i < num:
                    break
                dp[i] += dp[i - num] # 所有和为i-num的组合加上当前元素可以形成和为i的新组合

        return dp[target]

代码虽然短，但对于很久没写dp的人来说还是需要理解一会的。。动态规划通过构建一个解决方案的部分问题来解决整个问题，通常涉及填充一个或多个DP表（在这个问题中，是一个一维数组）。对于这个特定问题，DP数组的每个位置 i 代表了组成和为 i 的不同组合数。

初始化

我们初始化 dp[0] = 1。这意味着，总和为0的组合方式只有一种，即不选择任何数字（空集合）。这是动态规划的基础。

递推关系

对于每个可能的 i（从1到 target），我们考虑所有可能的 nums 中的数字 num，如果当前数字 num 小于或等于 i，那么 num 可以成为一个潜在的组合部分。

我们的更新规则是 dp[i] += dp[i - num]，它基于这样的逻辑：

• 如果你已经知道了组成和为 i - num 的所有可能的组合数（存储在 dp[i - num] 中），那么每一种组合都可以通过添加 num 来形成一个新的和为 i 的组合。
• 因此，你可以将这些新增的组合数加到 dp[i] 上。