【LeetCode】动态规划—377. 组合总和 Ⅳ（附完整Python/C++代码）-Python代码

class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        # 初始化dp数组，dp[i]表示凑成金额i的排列组合数
        dp = [0] * (target + 1)
        dp[0] = 1  # 凑成金额0的方式有1种（不选任何数字）

        # 动态规划计算
        for i in range(1, target + 1):
            for num in nums:
                if num <= i:
                    dp[i] += dp[i - num]
        
        return dp[target]  # 返回凑成目标target的排列组合数

Python代码解释

1. 初始化：定义 dp 数组，dp[i] 表示凑成金额 i 的排列组合数，初始时 dp[0] = 1。
2. 动态规划递推：遍历每个目标值 i，然后遍历 nums 数组，检查每个数字是否可以组合成 i。
3. 返回结果：最终返回 dp[target]，即为凑成 target 的排列组合数。

---