[LEETCODE] 322: Coin Change(Python)

Coin Change - LeetCode

문제 설명

대표적인 DP 문제 중 하나인 최소 개수의 동전 문제이다.

나의 풀이

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        m=10**4+1
        dp=[m]*(amount+1)
        dp[0]=0
        for i in range(amount+1):
            for j in coins:
                if i-j>=0:
                    dp[i]=min(dp[i],dp[i-j]+1)
        if dp[amount]>=m:
            return -1
        else:
            return dp[amount]

시간복잡도

amount동전 개수만큼의 시간이 걸리므로 O(1210^4)해서 약 O(10^5)정도가 걸린다.