다이나믹 프로그래밍(동전 바꾸기)

문제: coins에 주어진 동전을 가지고 amount를 만들기 위한 최소한의 동전의 갯수는 몇개인가?

 

from typing import List

def CoinChange(coins : List[int], amount : int) -> int:
    dp_array = [-1] *  (amount + 1)
    dp_array[0] = 0

    MAXCNT = 9999999
    for idxSum in range(1, amount + 1):
        minCnt = MAXCNT
        for coin in coins:
            if idxSum - coin < 0:
                continue
            if dp_array[idxSum - coin] == -1:
                continue
            minCnt = min(minCnt, dp_array[idxSum - coin] + 1)
        dp_array[idxSum] = -1 if minCnt == MAXCNT else minCnt

    return dp_array[amount]

print(CoinChange(coins=[2,3,5], amount = 10))

출처 : (5) 코딩테스트, 초급, 동전바꾸기 - YouTube