The invigilator asks you to count the students in the exam hall. You count: 40. Ten minutes later she asks again. Do you re-count? Of course not — nobody entered, nobody left. You remember.
Now recall the ache from the recursion lesson: naive fib(50) makes ~4,000 crore calls, because fib(30) is recomputed over a lakh times — identically, and the function remembers nothing. Dynamic programming is the invigilator's common sense, scaled up: solve each subproblem once, write the answer down, look it up forever after. Three added lines of code, and exponential collapses to linear. The name is intimidating; the idea is a notebook.
The two tests a problem must pass
DP applies when a problem has BOTH properties:
- Overlapping subproblems — the recursion asks the same smaller question repeatedly. fib(n) re-asks fib(k) constantly. Contrast merge sort: its two halves never repeat a question — which is why merge sort is D&C, not DP, and why adding a cache to it buys nothing.
- Optimal substructure — the best answer builds from best sub-answers: the shortest route to Pune via Lonavala contains the shortest route to Lonavala.
And the price tag, worth memorising as a formula: DP cost ≈ number of distinct states × work per state. fib has n+1 distinct states at O(1) each → O(n).
Cure 1: memoisation (recursion + a notebook)
def fib(n, memo={}):
if n <= 1:
return n
if n not in memo: # first time asked?
memo[n] = fib(n - 1) + fib(n - 2) # compute ONCE
return memo[n] # every repeat: a dict lookup
print(fib(50))Result
12586269025
Compare with the naive version: the recursion is untouched — we only added "check the notebook first; write into it after." Every distinct input is computed once; every repeat costs O(1). The 2ⁿ call tree collapses into a chain of 50 computations. This top-down style is memoisation: keep the natural recursive shape, add a cache. (In real code, @functools.lru_cache is the notebook as a one-line decorator; in interviews, write the manual version so the mechanism is visible.)
Cure 2: tabulation (fill the table upward)
The same computation, upside down. Instead of starting at fib(50) and recursing down, start at the base cases and fill a table upward, each entry built from entries already filled:
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # reads only FILLED cells
return dp[n]Same answers, same O(n), opposite direction — and a genuine trade-off, not a style choice. Memoisation: easier to write (the recurrence stays visible), computes only needed states, but rides the call stack (Python's ~1000-frame limit). Tabulation: no recursion at all, friendlier constants, and unlocks the space trick below — but computes every state and makes you order the filling correctly. Interviews routinely ask you to convert one into the other; do it once on fib and it's mechanical forever.
The space trick: keep what the recurrence reads
Stare at the tabulated loop. Which cells does dp[i] actually read? Only dp[i−1] and dp[i−2]. Everything older is dead storage — so keep two variables instead of an array:
def fib(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1O(n) time, O(1) space. The general move: ask what the recurrence reads, and store only that. Many 2-D DPs (knapsack, LCS — next lesson) read only the previous row, so two rows suffice: O(n·m) space becomes O(m). "Can you optimise the space?" is the single most predictable DP follow-up in existence, and this question is always its answer.
The real skill: defining the state
Fibonacci is training wheels — its state was handed to us. Real DP begins with a sentence YOU must write before any code:
"dp[i] = ⟨precise meaning in plain words⟩"
Take climbing stairs: you climb 1 or 2 steps at a time; how many distinct ways to reach step n? State: dp[i] = number of distinct ways to stand on step i. Now derive the recurrence with the master question — condition on the LAST decision: the final move was a 1-step from i−1, or a 2-step from i−2. Those route-families are disjoint (different last moves) and exhaustive (no other moves exist), so… add them: dp[i] = dp[i−1] + dp[i−2].
One more, to see the same ritual again — house robber: rob non-adjacent houses for maximum loot. State: dp[i] = best loot using houses 0..i. Last decision at house i: rob it (then i−1 is forbidden: add dp[i−2]) or skip it (keep dp[i−1]): dp[i] = max(dp[i−1], dp[i−2] + arr[i]).
The ritual: state meaning → condition on the last decision → base cases → fill order. The table is just this ritual's residue. Every DP problem in the next lesson yields to it.
Dry run: climbing stairs, cell by cell
n = 6 stairs, steps of 1 or 2. dp[i] = ways to stand on step i. dp[1] = 1 (one 1-step) dp[2] = 2 (1+1, or one 2-step) dp[3] = dp[2] + dp[1] = 3 dp[4] = dp[3] + dp[2] = 5 dp[5] = dp[4] + dp[3] = 8 dp[6] = dp[5] + dp[4] = 13 <- answer sanity-check dp[3] by brute force: 1+1+1, 1+2, 2+1 = 3 ✓
Two habits hiding in that trace, both worth stealing: say the state meaning before filling (it's the row that makes every other row make sense), and verify one small cell by brute force before trusting the table — the cheapest recurrence-bug detector there is.
The rematch: DP corrects greedy's coins
Last lesson ended with greedy's defeat: coins {1, 3, 4}, amount 6 — greedy grabbed the 4 and paid 3 coins; the optimum is 3+3. Watch DP handle the identical problem with the ritual.
State: dp[a] = fewest coins to make amount a. Last decision: which coin was used LAST? It was a 1, a 3, or a 4 — so try all three continuations and take the cheapest:
def min_coins(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount # dp[0] = 0: zero coins make zero
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1) # last coin was c
return dp[amount] if dp[amount] != INF else -1
print(min_coins([1, 3, 4], 6))Result
2
dp[6] = 1 + min(dp[5], dp[3], dp[2]) = 1 + min(2, 1, 2) = 2 — two threes, greedy corrected. DP is the systematic lookahead greedy refused to pay for: every choice considered at every state, at O(states × choices) cost — here 6 × 3 — instead of exponential. This greedy-counterexample-becomes-DP-example pairing is the cleanest one-two in algorithms; carry it into interviews whole.
What if...?
What if the amount can't be made — coins {3, 5}, amount 4? The INF sentinel survives to the end; return −1. Sentinels + a final check is the standard impossible-case pattern.
What if my memo key misses part of the state? Then two different questions collide in the notebook and answers corrupt silently — the nastiest DP bug. The key must be exactly the arguments that determine the answer, all of them.
What if the recursion depth explodes — n = 10⁵ in Python? Memoisation hits the ~1000-frame wall; switch to tabulation, which is why owning both directions matters.
What if there's nothing to remember? If no subproblem ever repeats (merge sort, subsets), a cache is pure overhead — DP's first test failed, and that's fine. Not every recursion wants a notebook.
Common mistakes
- Coding before writing the state's meaning in one sentence — the root cause of most DP failure.
- Memoising on an incomplete key — silent corruption.
- Wrong base cases — verify dp[0], dp[1] against brute force before trusting anything.
memo=as a default argument persists across calls — fine in interviews if you SAY it; use lru_cache or pass the dict in real code.- Calling merge sort DP, or thinking DP requires tables — overlapping subproblems + optimal substructure define it, not the furniture.
- Forgetting the space follow-up — always check what the recurrence reads.
How do I recognise DP problems?
- "count the ways" to do something with overlapping choices → DP (stairs, paths, decodings).
- "minimum/maximum cost" where greedy has no safe local choice → DP (coin change, house robber).
- Your correct recursion is too slow and its call tree repeats states → memoise it; that IS DP.
- "would knowing the answer for the first k elements help extend to k+1?" — if yes, a state definition is hiding there.
Next lesson turns recognition into a routing table: most interview DP belongs to four families, and naming the family is half the solution.
Quick revision
| Concept | One-liner |
|---|---|
| When DP applies | overlapping subproblems + optimal substructure |
| Memoisation | top-down recursion + cache; computes needed states only |
| Tabulation | bottom-up table; no stack risk; enables space tricks |
| Cost formula | distinct states × work per state |
| The ritual | state meaning → last decision → base cases → fill order |
| Space | store only what the recurrence reads |
One thing to remember
If the same smaller problem keeps appearing, solve it once and remember the answer. That's all DP is — the intimidating name is historical accident, the idea is a notebook.
Practice Zone — PYQs from real selection rounds
Six MCQs, then three builds: Fibonacci three ways with costs, climbing stairs filled cell by cell, and the coin-change table that corrects greedy.
Dynamic programming applies when a problem has:
Asked in
Memoised fib(n) runs in O(n) because:
Asked in
Memoisation vs tabulation — which statement is correct?
Asked in
Climbing stairs: you climb 1 or 2 steps at a time. Ways to reach step n obeys:
Asked in
Tabulated fib uses an array dp[0..n]. The standard space optimisation is:
Asked in
House robber: rob non-adjacent houses [2, 7, 9, 3, 1] for maximum loot. The recurrence for dp[i] (best using houses 0..i) is:
Asked in
Hands-on tasks:
Write fib(10) three ways — naive recursion, memoised, tabulated with O(1) space — and give each version's time and space complexity.
Asked in
Steps of 1 or 2, n = 6 stairs. Fill dp[1..6] cell by cell, stating what each cell means before computing it.
Asked in
Coins {1, 3, 4}, amount 6 — the exact case that broke greedy in lesson 6. Fill the DP table dp[0..6] and read off the answer.
Asked in
FAQ
Why is it called 'dynamic programming'? Nothing seems dynamic.
Historical accident: Richard Bellman chose the name in the 1950s partly because it sounded impressive to funding bureaucrats — "programming" meant planning, not coding. Ignore the name; think "recursion with memory" and everything fits.
How do I FIND the state for a new problem?
Ask: what is the minimum information that determines the answer to the rest of the problem? Usually a position/index, plus whatever constraint carries forward (remaining capacity, the last choice made). Litmus test: if two different histories reach the "same state" but have different futures, the state is incomplete — add the missing dimension.
Memoisation or tabulation in an interview?
Start with memoisation — it's your recursive solution plus three lines, and the derivation stays visible. Offer tabulation when asked or when depth would break recursion limits. Mention the space optimisation unprompted at the end: that sequence reads as mastery.
Is Kadane's algorithm (max subarray) DP?
Yes — state: best subarray ENDING at i; recurrence: extend or start fresh (best_here = max(x, best_here + x)); space already optimised to O(1). It's DP so compressed it looks like a trick — and the O(n) answer to the D&C lesson's max-subarray, closing that loop.
The notebook is yours. Next, the four families that cover most DP interviews — recognise the family and the table fills itself — Lesson 8: DP Patterns →