Today's Challenge

https://leetcode.com/problems/coin-change

Coin Change - LeetCode

단순한 DP 문제 중에 하나.
동전 리스트 순서대로 업데이트시켜주면 된다.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [math.inf] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for i in range(coin, amount+1):
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        
        return -1 if dp[-1] == math.inf else dp[-1]