Skip to content
Back to AlgorithmsAll lessons

Algorithms

Coin Change (Minimum Coins)

O(amount × number of coin types) time — for every amount, you check every coin once · O(amount) space for the table.

The idea, in plain English

This is the honest way to make change. It takes no shortcuts, and never assumes the biggest coin is always the smart pick. For every amount from 1 up to the target, you ask: what is the fewest coins that make exactly this much, built from answers you already worked out for smaller amounts? By the time you reach the target amount, you have genuinely tried every combination, not just the greedy-looking one.

How it works

  1. 1Make a table where table[amount] holds the fewest coins needed to make that exact amount. Start table[0] at 0, since zero coins make zero amount, and mark everything else as 'not yet known'.
  2. 2For every amount from 1 up to the target, try each coin. If the coin fits, check whether 'one more coin' plus the best answer for the remaining amount beats what is currently in the table.
  3. 3After you fill the whole table, table[target] holds the answer — or a sign that it is impossible, if no combination of coins can reach that exact amount.

When you'd use it

Use it to make exact change with coin systems that do not work well with the greedy approach, or for any 'fewest steps to reach an exact total' problem — real currency systems, token or resource costs, or the minimum moves in a game where each move has a fixed cost.

Common beginner mistakes

  • Trusting the greedy approach, always grabbing the biggest coin, to give the true minimum. With coins like [1, 3, 4], greedy on amount 6 grabs a 4 then two 1s, for 3 coins total, while the true best is 3 + 3, for 2 coins. Only this table-based approach is guaranteed correct.
  • Forgetting to handle the impossible case. If no combination of coins reaches the exact amount, that table cell should stay marked unreachable, not silently show a wrong number.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Amount: 6
Coins available: 1 3 4
Minimum coins needed: 2
Amount: 3
Coins available: 2 5
Minimum coins needed: -1

See it in motion

Watch the table fillCoin changeO(amount × number of coin types) time — for every amount, you check every coin once · O(amount) space for the table.

Ready. Fill the table amount by amount, one coin at a time.

1 3 4
Coins
6
Amount
0
Attempts
—
Min coins
Computing dp[i]Reads dp[i − coin]AnswerNot settled yet

Not sure this is the right topic? See the learning paths → or where this leads →