LeetCode 322 ·
Medium
Coin Change
Return the fewest coins that sum to a target amount, or −1.
Try it
Step through the core mechanic. The simulator below runs the dynamic programming shape this problem is built on.
Interactive · Coin Change — dp[amount] dp[a] = min over coins c of dp[a−c] + 1
| 0 | · | · | · | · | · | · |
0123456
dp[0] = 0; others = ∞
The approach
dp[a] = min over coins c of dp[a−c] + 1, building amounts 0..target. Each amount tries every coin; unreachable amounts stay at infinity.
| Aspect | Value |
|---|---|
| Pattern | Dynamic programming |
| Recognise it by | Fewest coins to make an amount — unbounded knapsack. |
| Time complexity | O(amount·coins) |
| Space complexity | O(amount) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.