题目
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The answer is guaranteed to fit in a 32-bit integer.
解题思路
dp[i]表示构成i有多少种方法，dp[target]为所求 dp[i] = sum(dp[i - n]) for n in nums if n <= i dp[0] = 1
代码
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [1]
for i in range(1, target + 1):
dp.append(sum([dp[i - n] for n in nums if n <= i]))
return dp[target]
