Dynamic Programming Intro
- Identify overlapping subproblems and optimal substructure in a problem statement
- Convert an exponential recursion into memoized top-down DP
- Convert memoization into bottom-up tabulation and compare the trade-offs
- Solve the 1D classics (climbing stairs, house robber) and a 2D grid problem
- Judge when DP is overkill and brute force or greedy is fine
| Spaced-rep warm-up: due cards (binary search, recursion, sorting) | 10 min |
| ELI5 + tech read; watch values flow through the dp-grid visualizer | 18 min |
| Guided: exponential→memo→table, robber + grid paths | 42 min |
| Practice: coin change | 20 min |
| Project: DP toolkit + recognition card | 20 min |
| Quiz + flashcards | 10 min |
Builds on: Day 27 — Recursion & divide/conquer (memoized fib) · Day 22 — Big O & complexity · Day 12 — Decorators & lru_cache
You are solving a jigsaw-puzzle marathon, and the organizers are lazy: many puzzles are repeats. The naive contestant re-solves every repeat from scratch. The smart one keeps a notebook — "puzzle #47: done, here is the picture" — and when a repeat appears, copies the answer in five seconds. That notebook is dynamic programming.
The trick only pays when two things are true. First, the same sub-puzzles must actually REPEAT — Day 27's fib exploded precisely because fib(40) re-solves fib(38) hundreds of thousands of times. Second, big answers must be buildable from small ones: "the best way up 10 stairs" is decided by the best ways up 8 and 9 — you never need to reconsider HOW you reached step 8, only the count. When both hold, an exponential mountain of repeated work collapses into a small table of distinct entries, each computed once.
Two ways to keep the notebook: solve top-down and jot answers as you happen to need them (memoization — recursion plus a cache), or fill the notebook in order from puzzle #1 up, knowing each entry only needs earlier ones (tabulation — a loop and an array). Same table, opposite directions.
DP is the interview boss battle — the topic hiring loops use to separate pattern-matchers from problem-solvers — and Day 35's drill and Day 179's gym both feature it. But you have already met production DP without the name: Day 12's lru_cache IS memoization, and caching expensive LLM calls keyed by input (Day 107, Day 156) is the same economics — pay once, look up forever, spend memory to buy time. Edit distance — a 2D DP — powers the fuzzy string matching inside spell-checkers and diff tools. The recognition skill ("these subproblems repeat") transfers to every caching decision you will ever make.
Remembering solved puzzles — counting grid paths with a table
step 1 / 6| c0 | c1 | c2 | c3 | |
|---|---|---|---|---|
| r0 | ? | ? | ? | ? |
| r1 | ? | ? | ? | ? |
| r2 | ? | ? | ? | ? |
How many paths from top-left to bottom-right, moving only right or down? Brute force walks every path — exponential. DP instead fills a table where each cell stores "paths that reach ME".
Guided practice
Exponential → memo → table, measured
20 min- Create
dp_lab.py. Time naiveclimb(35)(starter) — the pure recursion. Feel the exponential pain (seconds). - Add
@functools.lru_cacheand re-time climb(35), then climb(500). From seconds to microseconds — say why in complexity terms: 2^n repeated calls collapsed into n distinct states, each O(1). - Now write
climb_table(n)bottom-up with two variables (O(1) space). Verify all three agree on n = 1..20. - Try naive-recursive climb_memo(4000) — RecursionError — then climb_table(4000): instant. Record the lesson: memoization inherits recursion limits; tabulation does not.
- Write the four-step method for stairs in comments ABOVE the code: state meaning, recurrence, bases, answer location. This writing habit is the interview skill.
House robber + grid paths, think-aloud
22 min- Classic — house robber. Think aloud through the four steps: "STATE: best[i] = max loot using houses 0..i. CHOICE at house i: skip → best[i-1], or rob → best[i-2] + v[i]. RECURRENCE: max of the two. BASES: best[0] = v[0], best[1] = max(v[0], v[1])." Implement bottom-up with two variables.
- Test on [2, 7, 9, 3, 1] → 12 (rob 2+9+1) and the adversarial [2, 1, 1, 2] → 4 — the case that kills the "rob every other house" greedy. Say why greedy fails: local alternation is not optimal structure.
- Classic — unique grid paths. Think aloud: "STATE: paths[r][c] = ways to reach (r, c) going only right/down. RECURRENCE: sum of the cell above and the cell to the left. BASES: top row and left column are all 1." Fill the table for a 3×7 grid → 28.
- Print the filled 2D table as rows and trace one cell's value by pointing at its two parents — the dp-grid visualizer shows the same flow. Then the recognition drill: which earlier problem was secretly this? (Pascal's triangle; combinatorics C(m+n-2, m-1) — check it.)
On your own
Coin change (fewest coins)
20 minGiven coin denominations and a target amount, return the FEWEST coins that make the amount, or -1 if impossible. Example: coins [1, 4, 5], amount 8 → 2 (4+4). Note the greedy trap: largest-coin-first gives 5+1+1+1 = 4 coins. Wrong.
Run the four-step method in comments before coding. Constraints: O(amount × coins) tabulation. Test: ([1,4,5], 8) → 2, ([2], 3) → -1, ([1], 0) → 0.
Hints: state dp[a] = fewest coins for amount a; recurrence dp[a] = 1 + min(dp[a - c] for usable c); base dp[0] = 0; use a sentinel (inf) for unreachable amounts and translate to -1 at the end.
The DP recognition card + toolkit
Two deliverables. (1) dsa/dp.py: today's four problems (stairs, robber, grid paths, coin change), each with its four-step comment block and tests including the greedy-killer cases. (2) dp_recognition.md: your personal recognition card — the 4 signals a problem wants DP ("count the ways…", "min/max cost to reach…", choices with overlapping futures, feasibility of building a target), the memo-vs-table decision in two sentences, and the greedy-vs-DP lesson from coin change in your own words. This card gets drilled tomorrow (Day 35) and again on Day 179. Commit both.
Common mistakes & misconceptions
- Coding before defining the state in words. "dp[i] = …what exactly?" — if you cannot finish that sentence, the recurrence will be wrong.
- Calling any recursion+cache "DP" — merge sort's halves never repeat, so caching buys nothing. DP needs OVERLAPPING subproblems.
- Trusting greedy where DP is needed: coin change with [1,4,5] breaks largest-first. If a local choice can be globally wrong, you need DP (or a proof greedy works).
- Off-by-one base cases: is dp[0] "zero items" or "the first item"? Decide, write it down, and make tests hit n = 0 and n = 1.
- Memoizing on unhashable or unnecessary state — lru_cache needs hashable args, and dragging a whole list into the key when an index suffices explodes the state space.
- Forgetting that memoized recursion still hits Python's recursion limit (~1000 frames). Deep chains (n = 4000) want tabulation.
Q1. What TWO properties must a problem have for DP to beat brute force?
Q2. Memoized climb(4000) crashes with RecursionError but the tabulated version works. Why?
Q3. For coins [1, 4, 5] and amount 8, greedy largest-first returns 4 coins (5,1,1,1). DP returns 2 (4,4). What does this show?
Go deeper — curated resources
- Edit distance — the 2D shape you will meet again — Sketch the dp[i][j] table for transforming "cat" → "cart" (insert/delete/replace). Same grid flow as unique paths, with a 3-way min. Full treatment lands in interview prep.
- Timed the exponential→memo collapse and explained it in complexity terms
- Robber passes [2,1,1,2]; coin change passes the greedy trap
- Every solution carries its four-step comment block
- Recognition card committed and linked from the README
- Quiz ≥ 2/3
← Back: Day 27's memoized fib was DP without the name, and Day 12's lru_cache is the memoization tool. Grid paths is Day 31's path-counting on an implicit DAG — tabulation IS topological order.
Forward →: Tomorrow's drill (Day 35) tests recognition under time pressure, and Day 179 drills the 2D family (LCS, edit distance). The pay-once-look-up-forever economics returns as response caching on Day 107 and semantic caching on Day 156.