March 24
Coin Change
How to move away from blind combinations and build a DP that searches for the minimum cost for each value up to the target.
Dynamic Programming Intermediate 25 min TypeScript
Given an array coins of different coin values and an integer amount, return the minimum number of coins needed to make up amount.
If it is impossible to make that amount, return -1.
You may use each coin as many times as needed.
Example:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Because 11 = 5 + 5 + 1.
What to notice before coding
- The goal is to minimize the number of coins, not count combinations.
- Every value smaller than `amount` can become a subproblem.
- If an intermediate value is impossible, it cannot help build bigger values.
Common mistakes
- treating the problem like counting ways
- forgetting to mark impossible states with a sentinel value
Step 1 - Translate what the prompt is really asking
This problem looks like a combinations problem.
But the prompt does not ask:
- how many ways exist
It asks:
- what is the minimum number of coins
That changes the kind of state you need.
Step 2 - Write the recursive baseline
The natural baseline is:
- for the current value, try every coin
- solve the remaining value recursively
- keep the smallest valid result
It works.
But it recomputes the same remaining values many times.
Step 3 - Define the right state
The useful question becomes:
- what is the minimum number of coins needed for every value from
0toamount?
That suggests:
dp[value] = minimum number of coins to form value
Step 4 - Build the transition
If you are computing value and try using coin coin, the remainder is:
value - coin
If that remainder was possible, the new candidate answer becomes:
dp[value - coin] + 1
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function coinChange(coins: number[], amount: number): number {
// your solution here
return -1
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(amount * coins.length)
Space: O(amount)
Solution 1 - Recursion trying every coin before memoization
Good baseline because it makes the subproblem visible.
export function coinChange(coins: number[], amount: number): number {
function solve(remaining: number): number {
if (remaining === 0) {
return 0
}
if (remaining < 0) {
return Infinity
}
let best = Infinity
for (const coin of coins) {
best = Math.min(best, solve(remaining - coin) + 1)
}
return best
}
const answer = solve(amount)
return Number.isFinite(answer) ? answer : -1
}The issue is not the idea. It is the repeated work.
Solution 2 - Bottom-up dynamic programming with 1D state
Now each value is solved once.
export function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity)
dp[0] = 0
for (let value = 1; value <= amount; value += 1) {
for (const coin of coins) {
if (coin <= value) {
dp[value] = Math.min(dp[value], dp[value - coin] + 1)
}
}
}
return Number.isFinite(dp[amount]) ? dp[amount] : -1
}The strong reasoning here is building the answer from smaller values to larger ones.
What to say in the interview
A strong short explanation would be:
This is a minimization problem, not a counting problem. So I define
dp[value]as the minimum number of coins needed for that value. For each value, I try every coin and improve the answer usingdp[value - coin] + 1. At the end, if the final state is still impossible, I return-1.
That shows that you:
- chose the right state
- separated impossible cases from valid ones
- explained the transition without reciting a formula
When this pattern shows up again
The same pattern comes back when you need to:
- minimize cost or count
- build a 1D dynamic programming state
- reuse subproblems by value
- distinguish “no solution exists” from “the solution is large”
The point is not memorizing
coinChange.
The point is learning how to model minimization in dynamic programming.