LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

Coin change with dynamic programming, visualized

Coin change (LeetCode 322) asks for the fewest coins that add up to an amount. Being greedy fails — with coins 1, 3 and 4 it pays 6 as 4 + 1 + 1 instead of 3 + 3 — so the answer has to be built from smaller answers.

How it works
Python
coins = [1, 3, 4]
amount = 9
big = amount + 1

dp = [big] * (amount + 1)
dp[0] = 0

for value in range(1, amount + 1):
    for coin in coins:
        if coin <= value:
            dp[value] = min(dp[value], dp[value - coin] + 1)

print(dp[amount] if dp[amount] != big else -1)

How coin change works

dp[v] holds the fewest coins needed to make the amount v. dp[0] is 0 and everything else starts at an impossible value. For each amount from 1 upwards, try every coin that fits: using it costs one coin plus the best answer for v − coin, which is already in the table. Keep the smallest.

The example uses coins [1, 3, 4] and the amount 9, and the table finishes with dp[9] = 3.

What to watch for when it runs

  1. The dp array is drawn as a row of cells, filled from left to right.
  2. Every update reads a cell further to the left — an answer that is already final.
  3. dp[6] settles on 2 (3 + 3): the case a greedy choice gets wrong.

Time and space complexity

Time
O(amount × coins)
Space
O(amount)

Each amount tries each coin once. If no combination works the cell keeps its impossible value, and the answer is −1.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.