[DP] 동전 교환 - 최소 개수

문제

$K$가지 동전이 있고 각 동전은 무한히 쓸 수 있다. 금액 $M$을 정확히 만드는 데 필요한 동전의 최소 개수를 구하라. 만들 수 없으면 $-1$을 출력한다.

접근

$dp[m]$을 "$m$원을 만드는 최소 동전 개수"라 하면, 마지막에 쓴 동전 하나를 빼고 본다.

$dp[m] = \min_{c \le m} \bigl(dp[m-c] + 1\bigr), \quad dp[0] = 0$

닿을 수 없는 금액은 무한대로 두고, 마지막에 $dp[M]$이 무한대면 $-1$.

입출력 예시

입력:
3 6
1 3 4
출력: 2