1. Impossible sentinel
Unknown totals start as impossible.
Array(amount + 1).fill(Infinity)Typorithm · medium
Coin Change
▷ Interactive algorithm labcoin-change-dpdynamic-programmingunboundedminimization
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Coin Change
Dynamic Programming
Coin Change stores the fewest coins needed for every amount up to the target.
Each amount is a subproblem.
For every amount, try every coin that fits.
Infinity marks amounts that cannot yet be formed.
Preparing algorithm lab…
01
State: min coins for total.
02
Base: dp[0] = 0.
03
Transition: min(existing, dp[total-coin] + 1).
04
Return -1 if target stays impossible.
function coinChange(coins, amount) {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let total = 1; total <= amount; total++) {
for (const coin of coins) {
if (coin <= total) {
dp[total] = Math.min(dp[total], dp[total - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Zero amount
Zero coins are needed to make amount 0.
dp[0] = 03. Try every coin
Each total can be reached by taking any valid coin.
for (const coin of coins)4. Min coins
Take one coin plus the best way to make the remaining amount.
dp[total] = Math.min(dp[total], dp[total - coin] + 1)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.