377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/description/

nums를 조합하여 target을 만들 수 있는 개수를 반환하는 문제이디.

대표적인 dp문제인 동전 문제 (예. [50원,100원,500원]과 금액(예.2000)이 주어졌을 떄 만들 수 있는 경우의 수)와 비슷하다고 생각하여 dp를 이용하여 풀었다.

시간복잡도는 O(nums*target)

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 n in nums:
                if n<=i:
                    dp[i] += dp[i-n]
        return dp[target]