Coin Change
Coin Change is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is unbounded knapsack dp, and a good solution runs in O(amount · coins) time.
Problem
Return the fewest reusable coins needed to total amount, or -1 when no combination exists.
Examples
Example 1
Input
{"coins":[1,4,6],"amount":8}Output
2Example 2
Input
{"coins":[1,3,4],"amount":6}Output
2Example 3
Input
{"coins":[2,5,10],"amount":3}Output
-1Approach
Build the fewest coins for every amount from 0 up: each amount takes one coin plus the best answer for the amount minus that coin.
| Pattern | Unbounded knapsack DP |
|---|---|
| Time | O(amount · coins) |
| Space | O(amount) |
Watch out for
Amount 0 needs 0 coins; an amount that cannot be made returns -1.