Coin Change (fewest coins)

Make a target amount with as few coins as possible, given unlimited coins of each denomination. Greedy 'always take the biggest coin' works for real currencies and fails for others — so the table is built instead.

time O(amount × coins)

space O(amount)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

dp[0] = 0; dp[1..amount] = infinity
for a in 1..amount:
  for c in coins:
    if c <= a:
      dp[a] = min(dp[a], dp[a-c] + 1)
return dp[amount] or -1