Coin change

O(n·amount)

Given coin denominations and a target amount, coin change asks for the fewest coins that sum to it (each denomination available without limit). The DP table dp[i][a] holds the best answer for amount a using the first i denominations. Each cell is the better of two choices: skip this coin (copy the value from the row above) or use one more of it (one plus the cell `coin` columns to the left, in the same row, since the coin can repeat). Unreachable amounts stay blank. Filling the table is O(n·amount), and the bottom-right cell is the minimum. It's the textbook example of optimal substructure with overlapping subproblems.

DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. Amount 0 always needs 0 coins — that's the base column.
  2. For each cell, first copy the answer that skips this coin (the row above).
  3. If the coin fits, compare with 1 + the cell one coin-value to the left.
  4. Keep the smaller; the bottom-right cell is the fewest coins (blank means impossible).

Pseudocode

1coinChange(coins, amount):          # O(n·amount)2  dp[i][0] ← 0                       # amount 0 needs 0 coins3  for each coin i, amount a in 1..amount:4    best ← dp[i-1][a]                # skip this coin5    if a ≥ coin and dp[i][a-coin] reachable:6      best ← min(best, dp[i][a-coin] + 1)  # reuse coin7    dp[i][a] ← best8  return dp[n][amount]               # ∞ ⇒ impossible