Easy Problemsminimizationlinear

Coin Change – Minimum Coins to Make Sum

Given coin denominations and a target sum, with an unlimited supply of each denomination, find the fewest coins that add up to exactly that sum. Report -1 if the sum cannot be made at all.

Do this lesson first: coin change

Example input

coins = [1, 3, 4], amount = 12

Expected output

3

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[a] = 1 + min over every coin c <= a of dp[a - c]

The full derivation, why the last coin spent leaves behind a remainder whose own fewest-coins count is already known, lives in the flagship lesson at /courses/dynamic-programming/coin-change. This page assumes it and goes straight to the table.

dp[0] = 0 is given; see the flagship lesson for why making zero costs no coins. Every cell from a = 1 up depends only on smaller amounts (a - c for every coin c <= a), so filling left to right guarantees every candidate already holds a real value before it is read. Unlike maximum-segments, nothing here is ever unreachable: coin 1 is always available, so every amount can always be padded up to, only more or less cheaply.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 0 is given; see the flagship lesson for why making zero costs no coins. Every cell from a = 1 up depends only on smaller amounts (a - c for every coin c <= a), so filling left to right guarantees every candidate already holds a real value before it is read. Unlike maximum-segments, nothing here is ever unreachable: coin 1 is always available, so every amount can always be padded up to, only more or less cheaply.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

i=10

i=11

i=12

0

1

2

1

2

3

coin-change-minimum-coins.ts

1function coinChange(coins, amount) {
2 const dp = new Array(amount + 1).fill(Infinity);
3 dp[0] = 0;
4 for (let a = 1; a <= amount; a++) {
5 for (const c of coins) {
6 if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
7 }
8 }
9 return dp[amount];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

coin-change-minimum-coins.ts

1function coinChange(coins, amount) {
2 const dp = new Array(amount + 1).fill(Infinity);
3 dp[0] = 0;
4 for (let a = 1; a <= amount; a++) {
5 for (const c of coins) {
6 if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
7 }
8 }
9 return dp[amount];
10}

Where people go wrong

Assuming the largest coin that still fits should always be spent first. It should not: with coins {1, 3, 4}, making 6 by greedily spending a 4 first leaves 2, which then costs two more 1s, for 4 + 1 + 1, three coins total, while the true optimum is 3 + 3, two coins. Every candidate remainder has to be compared through the full table; there is no shortcut that skips checking the smaller coins too.

Count the number of distinct combinations that make the amount, instead of the fewest coins.
combine switches from a min over candidates plus one to a sum over candidates, and the coin loop has to sit outside the amount loop so each combination is counted once instead of once per ordering.
Allow only one coin of each denomination, instead of an unlimited supply.
dp[a] alone stops being enough state: it cannot say whether a given coin has already been spent, so a second dimension tracking which coins remain becomes necessary, the same shift that turns unbounded knapsack into 0/1 knapsack.

Coin change problem – Count Ways Painting Fence Algorithm