Coin Change

Problem

You have an unlimited supply of coins in each of the denominations listed in coins, and a target amount. Return the smallest number of coins whose values sum exactly to amount. If no combination of the given coins can produce amount, return -1.

• coins holds up to about a dozen distinct positive denominations, each of which can be a large positive integer (large enough that you should not index anything by coin value).
• amount is a non-negative target up to roughly ten thousand.

Examples

• coins = [1, 4, 6], amount = 13 → 3, using 6 + 6 + 1.
• coins = [3], amount = 5 → -1. Only multiples of 3 are reachable with a single 3-coin.
• coins = [1, 7, 10], amount = 14 → 2 (7 + 7). Greedy would take a 10 first and end at 10 + 1 + 1 + 1 + 1 = 5 coins, which is wrong.

Hints

1. Try the greedy approach of always taking the largest coin on coins = [1, 7, 10], amount = 14. What goes wrong?
2. If you had the optimal answer for every amount smaller than amount, how would you compute it for amount by considering only the last coin used?
3. This is unbounded knapsack: fewest[a] = 1 + min(fewest[a - c] for c in coins if c <= a), filled from 0 up to amount.