Coin Change
Problem Statement
You are given an integer array coins representing coin denominations and an integer amount. Return the fewest number of coins needed to make up amount. If that amount cannot be made by any combination of the coins, return -1. You may use each coin denomination an unlimited number of times.
Input
An array coins of positive denominations and a target amount.
Output
An integer: the minimum number of coins needed, or -1 if no combination can form the amount.
Constraints
- •
1 <= coins.length <= 12 - •
1 <= coins[i] <= 2^31 - 1 - •
0 <= amount <= 10^4
Examples
Example 1
coins = [1,2,5], amount = 11
3Example 2
coins = [2], amount = 3
-1Example 3
coins = [1], amount = 0
0Learning Objectives
- Recognise minimum-coin change as unbounded knapsack minimisation.
- Initialise unreachable states with a large sentinel and protect updates from impossible predecessors.
- Use ascending amount iteration because the same coin may be reused within one outer-loop iteration.
- Differentiate minimum-count DP from number-of-ways DP even though both use the coin-change family.
Intuition
For every amount a, imagine asking for the best last coin. If the last coin is coin, then before taking it we must have formed a - coin. So a candidate answer is dp[a - coin] + 1.
Because coins can be reused forever, this is unbounded knapsack. That changes the loop direction from the previous 0/1 problems. When processing a coin, we scan amounts upward so dp[a - coin] may already include the current coin. That is not a bug here; it is exactly how 5 + 5 becomes available while processing coin 5.
Unreachable amounts need a sentinel. Using amount + 1 works because no valid answer can require more than amount coins when all coin values are positive and coin 1 is the worst possible valid case.
Common mistakes
- ×Scanning amounts descending, which treats each coin denomination as usable once and breaks unbounded reuse.
- ×Initialising the table with zero for all amounts, making every amount look reachable.
- ×Returning the sentinel instead of converting unreachable amounts to -1.
- ×Confusing this minimisation problem with Coin Change II, which counts combinations rather than minimising coins.
State Definition
Let dp[a] be the minimum number of coins needed to form amount a using the coin denominations processed so far, with unlimited copies of those denominations. The answer is dp[amount] unless it remains unreachable.
State Transition
Base case: dp[0] = 0 because zero coins form amount 0. All other states start as a large sentinel.
For each coin, scan a from coin up to amount and apply dp[a] = min(dp[a], dp[a - coin] + 1) when dp[a - coin] is reachable.
The ascending scan is the core unbounded-knapsack detail. Since a - coin < a, the smaller amount may have been updated earlier in the same coin iteration, allowing the current coin to be used repeatedly. A descending scan would preserve the previous row and incorrectly make each coin denomination 0/1.
Solutions
Solution: 1D unbounded minimisation DP
Process each denomination and relax every amount from low to high. The low-to-high scan lets the current coin feed future amounts in the same iteration, which models unlimited supply.
Step-by-step
- Create a dp array of length amount + 1.
- Fill it with amount + 1 as the unreachable sentinel, then set dp[0] = 0.
- For each coin, scan amounts from coin through amount.
- If a - coin is reachable, try taking one more copy of this coin.
- Return -1 if dp[amount] is still the sentinel; otherwise return dp[amount].
O(coins.length · amount)
O(amount)
Each coin relaxes every relevant amount once.
Java implementation
Dry Run
Sample input
coins = [1, 2, 5], amount = 11. The table stores the minimum coins for each amount from 0 to 11.
| coin | amount scan | dp[0..11] after coin | key effect |
|---|---|---|---|
| start | none | [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] | Only amount 0 is reachable before any coin is processed. |
| 1 | 1 up to 11 | [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] | Ascending scan reuses coin 1 for every amount. |
| 2 | 2 up to 11 | [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6] | Amounts like 4 improve to 2 + 2 because coin 2 can be reused. |
| 5 | 5 up to 11 | [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3] | Amount 11 improves to 3 using 5 + 5 + 1. |
The final cell is dp[11] = 3. If it had stayed at the sentinel, the correct return value would be -1.
Complexity Analysis
This is pseudo-polynomial in the amount, not in the numeric size of the input encoding. For standard interview constraints, O(coins.length · amount) is expected.
1D unbounded minimisation DP
O(coins.length · amount)
O(amount)
Each coin relaxes every relevant amount once.
Interview Tips
Say the phrase unbounded knapsack and immediately contrast it with 0/1: here the amount loop goes upward because reusing the same coin is allowed. Also explain the sentinel choice; it prevents impossible states from looking like zero-coin solutions.
Likely follow-ups
- Return the actual coins used in one minimum solution.
- What if every coin denomination had a limited inventory?
- How would you count all combinations instead of minimising the number of coins?
- How would the solution change if coin order mattered?
Similar Problems
Key Takeaways
- Coin Change is unbounded knapsack minimisation over the target amount.
- Use a sentinel for unreachable amounts and convert it to **-1** at the end.
- Amount iteration is ascending because the current coin may be reused immediately.
- The recurrence takes a minimum over the previous amount plus one coin.