377. Combination Sum IV

377. Combination Sum IV

可以分解成子问题，且子问题有重复，很明显DP问题
DP是一个target+1维的数组，DP[i]表示target=i时的解

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """ 
        dp = [0 for i in range(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[-1]