DPDynamic Programming

Coin Change (min coins)

Find the fewest coins that sum to an amount (or count the ways) using unlimited coins of given denominations.

coins | amount — Coin values, a pipe, then the amount — e.g. "1, 3, 4 | 6". Up to 5 coins, amount ≤ 15

0	1	2	3	4	5	6
0	∞	∞	∞	∞	∞	∞

1/20dp[a] = fewest coins that sum to a. Amount 0 needs 0 coins; everything else starts at ∞ (unknown / impossible).

Cell being filledDependency readBase caseComputedReconstructed choice

PseudocodeLearn Coin Change →

1dp[0] = 0; dp[1..A] = ∞
2for a in 1 .. A:
3  for coin in coins:
4    if coin <= a and dp[a-coin] + 1 < dp[a]:
5      dp[a] = dp[a-coin] + 1; from[a] = coin
6return dp[A] (∞ means impossible)

Variables

Complexity

best O(amount · k)

avg O(amount · k)

worst O(amount · k)

space O(amount)

Speed