Manjusaka

09-09 leetcode-0377

链接 377. Combination Sum IV

题目

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

题解

最基础的 DP 题目，状态转移方程 dp[i] = dp[i] + dp[i - num]

class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for num in nums:
                if num <= i:
                    dp[i] += dp[i - num]
        return dp[target]