Coin Change
Find the fewest coins needed to make an amount, or report impossible.
Why does this pattern fit?
Restate the exact job
Find the fewest coins needed to make an amount, or report impossible.
Each amount depends on smaller amounts reached by removing one coin.
O(amount·coins) time · O(amount) space
Using zero as the default makes unreachable amounts look solved.
How to solve Coin Change
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Find the fewest coins needed to make an amount, or report impossible.
Why Dynamic programming fits
Each amount depends on smaller amounts reached by removing one coin.
State to maintain
dp[a] = minimum coins for amount a, initialized to infinity except dp[0]=0.
Transition
For each amount and coin, relax dp[a] from dp[a−coin]+1.
Time and space
O(amount·coins) time · O(amount) space
Counterexample to the tempting mistake
Using zero as the default makes unreachable amounts look solved.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.