DP is recursion with a memo
📖 Walk me through it — plain English
Dynamic programming (DP) just means: solve a big problem by first solving smaller versions of the same problem, and write down each small answer so you never recompute it. "Recursion" = a function that calls itself on a smaller input. A "memo" (short for memoization) = a notebook where you store answers you've already worked out. So DP is recursion plus a notebook. The lesson's whole point is: figure out the recursion first (the three thinking steps below), and the storing part is mechanical afterward.
The three things you must nail before writing any code: State — what does one subproblem mean? Here f(a) = the fewest coins that add up to amount a. Recurrence — how does a bigger answer lean on smaller ones? To make amount a, try laying down one coin c, then you still owe a − c, which you already solved: so f(a) = min over coins of f(a − c) + 1. Base case — the smallest answer you know for free: f(0) = 0 (zero coins make zero).
Analogy. Imagine paying an exact bill with the fewest physical coins. Instead of guessing the whole payment at once, you ask: "What's the cheapest way to make 1 cent? 2 cents? 3 cents?" and write each best answer on a sticky note. By the time you reach the real total, every smaller total already has a sticky note, so the final answer is one quick lookup-and-add. The code below isn't recursive — it fills those sticky notes in order from small to large (called bottom-up tabulation), but it's the same idea: never solve a subproblem twice.
Let's trace coins = [1, 4, 5], amount = 8. We build the row dp where slot a holds f(a). Start it all at infinity (∞ = "unreachable so far"), except slot 0 which is 0.
Why it works. Every slot only depends on smaller slots, and we fill left-to-right, so whenever we need f(a − c) it's already finalized — no slot is ever computed twice. Notice greedy "grab the biggest coin first" would take 5+1+1+1 = 4 coins for amount 8, but DP correctly finds 4+4 = 2 by actually comparing every option. Complexity: there are amount + 1 slots, and at each we try every coin once, so the work is O(amount × number_of_coins) time and O(amount) space for the row. That's the payoff of the memo: a problem that looks exponential if you re-explore every combination collapses to a simple double loop.
Always build the recursion first. Then add a cache. Only convert to bottom-up tabulation if it matters. Skipping the recursion is why candidates fail mid-DP.
- State. "f(i) = best answer considering first i elements." Be precise about what each parameter means.
- Recurrence. Express f(i) in terms of smaller subproblems. This is the entire problem.
- Base case. What's f(0)? f(empty)?
- Memoize / tabulate. Mechanical step once 1–3 are right.
Problem: fewest coins summing to amount, given coins.
- State: f(a) = min coins to make a
- Recurrence: f(a) = min(f(a - c) + 1) for each coin c with c ≤ a
- Base: f(0) = 0; unreachable = ∞
def coin_change(coins, amount):
INF = float('inf')
dp = [INF] * (amount + 1); dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a-c] + 1 < dp[a]:
dp[a] = dp[a-c] + 1
return dp[amount] if dp[amount] != INF else -1Minimum coins to make an amount — the four-step DP method in action: