Pattern this teaches:1D Dynamic Programming
Coin Change
A medium Dynamic Programming interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Dynamic Programming
- Sheets
- 3
- Core for
- 9 roles
The problem
You are given an integer array of coin denominations and a total amount. Find the fewest number of coins needed to make up that amount. If it is impossible, return -1.
Example 1
- Input
- coins = [1,4,6], amount = 14
- Output
- 3
- Why
- 6 + 4 + 4 = 14 with three coins; no two coins reach 14.
Example 2
- Input
- coins = [2], amount = 3
- Output
- -1
- Why
- It is impossible to make 3 with only coins of denomination 2.
Example 3
- Input
- coins = [1], amount = 0
- Output
- 0
- Why
- No coins needed when the amount is already 0.
Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
How to think about it
Updated 2026-09-29Every coin value reduces the remaining target by a fixed step, making the fewest coins to form any total depend purely on the fewest coins needed for smaller totals. Instead of asking which branch to take, build up answers by trying every coin from the bottom up: the optimal answer for any sum is one plus the cheapest predecessor.
Approaches, worst first
Recursive search
time O(k^amount) · space O(amount)
Try subtracting each coin denomination from the target and recurse on the remainder. Without caching it recalculates identical sub-amounts millions of times, generating an enormous tree that quickly exceeds the execution limit.
Memoized search
time O(amount * k) · space O(amount)
Run top-down recursion while storing the minimum coins needed for each remaining amount in a table. It trims duplicate work, but the recursion stack incurs overhead for deep targets.
Iterative bottom-up tableWrite this one
time O(amount * k) · space O(amount)
Initialize an array of size amount + 1 filled with infinity, set dp[0] = 0, and iterate from 1 to amount. For each amount, check every coin: dp[i] = min(dp[i], dp[i - c] + 1). It runs entirely in simple loops without call-frame overhead.
Where people lose marks · 4
- Initializing the array with 0 or -1 instead of an unreachable sentinel like amount + 1. If 0 is used as empty, min comparisons treat unreachable states as free.
- Target amount of 0 requires exactly 0 coins. Returning -1 or failing to handle 0 breaks the base case before any coin is examined.
- Coin values can exceed 2^31 - 1. When amount is small, accessing dp[i - coin] directly without checking if coin <= i leads to negative indexing or out-of-bounds reads.
- Assuming the greedy strategy of picking the largest coin first works. For coins [1, 6, 7] and amount 12, greedy takes 7 + 1 + 1 + 1 + 1 + 1 (6 coins) instead of 6 + 6 (2 coins).
Full solution
Iterative bottom-up table (the notes' recommended approach): dp[i] holds the fewest coins for amount i, filled with an unreachable sentinel (amount + 1) so min() never mistakes 'unreachable' for 'free'.
Python
def coin_change(coins: list[int], amount: int) -> int:
unreachable = amount + 1
dp = [unreachable] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
return dp[amount] if dp[amount] != unreachable else -1
JavaScript
function coinChange(coins, amount) {
const unreachable = amount + 1;
const dp = new Array(amount + 1).fill(unreachable);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const c of coins) {
if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
}
}
return dp[amount] === unreachable ? -1 : dp[amount];
}
The theory behind it
Dynamic Programming — the ground this problem stands on. All Dynamic Programming problems
What Dynamic Programming is
Dynamic programming is a method for solving a complex problem by breaking it into overlapping subproblems, solving each subproblem only once, and remembering the answers in a lookup table. Instead of recalculating identical questions over and over, future steps look up previous answers directly. By assembling these saved pieces from the bottom up or storing them during recursion, a task that would take billions of steps finishes in a fraction of a second.
When to reach for it
Reach for dynamic programming when questions ask for the maximum profit, minimum cost, total number of distinct ways to achieve a goal, or whether a target can be formed. Signals include overlapping choices where making a choice now affects what choices remain later, but greedy picking fails to find the true global optimum. If drawing a recursive decision tree reveals the same subproblem states repeating across branches, dynamic programming is needed.
How the pattern works
Identify the state variables that uniquely describe a subproblem, such as an array index and remaining capacity. Write the base cases first, representing states whose answers are known without calculation. Next, write the recurrence relation that expresses the current state using previously solved states, taking the minimum, maximum, or sum among your options. Build the solution either top-down by caching recursive returns in a memo table, or bottom-up by filling an array in topological dependency order. When each state depends only on the previous row, compress storage down to a single array.
More Dynamic Programming problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .