0

Coin Change

Medium

Fewest coins for each amount from zero upward. Each cell asks: which coin was the last one I used?

unbounded knapsackbottom up
TimeO(coins * amount)
SpaceO(amount)
Inputcoin values | target amount
0
1
2
3
4
5
6
min coins
0
inf
inf
inf
inf
inf
inf
cell being filledcells it readsreconstructed answer

Zero coins make amount zero. Everything else starts unreachable.

1 / 20
dp[0] = 0; dp[rest] = infinity
for amount from 1 to target:
for coin in coins:
if coin <= amount:
dp[amount] = min(dp[amount], dp[amount - coin] + 1)
Why it matters

Greedy fails here. With coins 1, 3 and 4, greedy makes 6 as 4+1+1 while the answer is 3+3.

Practise this
Coin ChangeMCoin Change IIMPerfect SquaresMCombination Sum IVM
Keyboard
space play← → stepr restartctrl K search

More in Dynamic Programming

Kadane (Maximum Subarray)
O(n)
Memoisation vs Brute Force
O(2^n) naive, O(n) memoised
0/1 Knapsack
O(n * W)
Longest Common Subsequence
O(n * m)
Longest Increasing Subsequence
O(n log n)
Minimum Path Sum
O(rows * cols)
Edit Distance
O(n * m)
Next visualiser
Longest Increasing Subsequence