Fewest Coins for Change
Medium1-D Dynamic Programming
Problem
A vending machine must pay out exactly amount cents using coins whose values are listed in coins. It has an unlimited supply of every coin value.
Return the fewest coins that add up to amount, or -1 if the amount cannot be made.
Example 1
- Input:
- coins = [1, 2, 5], amount = 11
- Output:
- 3
5 + 5 + 1.
Example 2
- Input:
- coins = [2], amount = 3
- Output:
- -1
Only even amounts can be made from 2-cent coins.
Example 3
- Input:
- coins = [1], amount = 0
- Output:
- 0
Constraints
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2^31 - 1
- 0 ≤ amount ≤ 10^4
Hint
Show the first hint
Greedy (always take the biggest coin) is wrong for coin sets like [1, 3, 4] and amount 6. Think about the last coin instead.
Walkthrough
How to approach it
01Clarify before coding
- Unlimited coins of each value? Yes.
- What if amount is 0? Zero coins.
- What to return when impossible? -1.
- Are coin values sorted or distinct? Not guaranteed; it does not matter for the DP.
02Brute force
Recursively subtract every coin from the amount and take the shortest path to 0. Memoising on the remaining amount gives a top-down DP with the same complexity as the table.
Cost: Without memo: exponential, since the same remaining amount is re-solved along every path that reaches it. With memo: O(amount·k) time, but a recursion depth up to amount, risky in Python for amount = 10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.