Given coin values and an amount, return the fewest coins that make up the amount. You can use each coin as many times as you like, and return minus 1 if it is impossible.
DSA Animator › DSA Revision › Dynamic Programming › Coin Change
Remember: try every coin as the last one. Greedy fails for general coin sets, so dynamic programming is needed. The video solves Coin Change (LeetCode 322, Medium) with the Unbounded Knapsack pattern from the Dynamic Programming topic, and you can replay every step in the interactive Coin Change animation.
Given coin values and an amount, return the fewest coins that make up the amount. You can use each coin as many times as you like, and return minus 1 if it is impossible.
For coins 1, 2, 5 and amount 11, the answer is 3. That is 5 plus 5 plus 1.
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 minus 1.
dp of 0 is 0, and dp of 1 is 1, using a single 1. dp of 2 is 1, using the coin 2, and dp of 3 and dp of 4 are 2. dp of 5 is 1, using the coin 5. The values continue 2, 2, 3, 3, then dp of 10 is 2, which is 5 plus 5. dp of 11 is 1 plus dp of 10, using the coin 1, which is 3. So the answer is 3.
In code, fill dp with amount plus 1, which acts as infinity, and set dp of 0 to 0. For each amount from 1 up, loop over the coins. If the coin fits, set dp of x to the smaller of dp of x and dp of x minus coin plus 1. Return dp of amount, or minus 1 if it is still infinity, so it's O of amount times coins.
Remember: try every coin as the last one. Greedy fails for general coin sets, so dynamic programming is needed.