Solution: Coin Change
Let's solve the Coin Change problem using the Dynamic Programming pattern.
Statement
Given an integer total
that represents the target amount of money and a list of integers coins
that represents different coin denominations, find the minimum number of coins required to make up the total amount. If it’s impossible to achieve the target amount using the given coins, return -1
. If the target amount is 0, return 0
.
Note: You can assume that we have an infinite number of each kind of coin.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.