You are given an integer array coins representing coins of different denominations and an integer amount. Return the fewest number of coins to make that amount. If impossible, return -1. You may use each coin infinite times.
coins = [1,2,5], amount = 113coins = [2], amount = 3-1Unbounded knapsack: each coin can be used multiple times. For each target amount a, we try every coin c that fits. If we use coin c, we need 1 + min coins for a−c, so candidate = dp[a−c] + 1. We keep the minimum. dp[0]=0 is the base case.
Greedily taking the biggest coin fails for some coin sets, like coins 1, 3, 4 and amount 6. Greedy picks 4, 1, 1, which is 3 coins, but 3 plus 3 uses only 2. Trying every combination recursively repeats the same amounts many times.
Let dp of x be the fewest coins needed for amount x. dp of 0 is 0, because no coins are needed. For any other amount, try every coin as the last coin used. Then dp of x is 1 plus the smallest dp of x minus coin. Amounts that cannot be made stay at infinity, which becomes −1.
Try every coin as the last one. Greedy fails for general coin sets, so dynamic programming is needed.
Run the animation above on your own input, or watch the 2:06 video explanation of Coin Change with a dry run and Java code.