Dynamic programming has a terrifying reputation and a one-line secret: the same subproblem always has the same answer, so compute it once and write it down. Everything else — memo dicts, bottom-up tables, the whole 1-D family — is bookkeeping around that sentence.
Chapter 19 ended on a betrayal: greedy picked coins from [1, 3, 4] for amount 6 and confidently produced the wrong answer. This chapter is where that problem — and every problem whose choices interact — goes to get solved honestly. DP is not a new kind of thinking. It's Chapter 18's recursion, plus the observation that you keep solving the same subproblems, plus a notebook.
We'll build the idea in the order you'd build it at a whiteboard: catch naive recursion red-handed repeating work, cache it (top-down memoization), flip the cache into a table filled in dependency order (bottom-up), then tour the 1-D family — Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence, Word Break — reading each recurrence straight off the problem's choices. The 2-D family (grids, string pairs, knapsacks) waits in Chapter 21.
Start with Climbing Stairs Easy: you climb a staircase of n steps, taking 1 or 2 at a time — how many distinct ways up? The recursive answer writes itself: to stand on step n, your last move came from step n−1 or step n−2, and those are the only options. So ways(n) = ways(n−1) + ways(n−2). It's Fibonacci wearing a gym outfit.
Run that recursion naively and something ugly happens: ways(5) calls ways(4) and ways(3); the ways(4) call also calls ways(3). Two full, identical computations of the same value — and it compounds every level down. The call tree has O(2ⁿ) nodes — the tree roughly doubles at every level — to compute a function with only n + 1 distinct inputs. At n = 50 you're doing quadrillions of calls to learn about fifty numbers.
That gap — exponentially many calls, linearly many distinct questions — is the disease DP cures. The textbook name is overlapping subproblems. The other textbook phrase, optimal substructure, just means the answer to a big state is assembled from answers to smaller states — which is exactly what your recurrence already claims. If you can write the recursion, you've already asserted both properties; you just haven't stopped paying for the overlap yet.
The fix is almost insultingly small. Keep a dictionary keyed by the argument. On entry, if the answer is already in the dict, return it; otherwise compute, store, return. That's memoization — top-down DP. The recursion still looks exponential, but every distinct state is computed exactly once and every repeat is an O(1) lookup: O(2ⁿ) collapses to O(n) — one honest computation per distinct state.
In Python this is literally one decorator: @lru_cache above your brute recursion, done. In Scala, memo.getOrElseUpdate(key, …) wraps the body. The practical consequence is huge for interviews: you never have to invent a DP solution from nothing. You write the brute-force recursion out loud — which Chapter 18 already taught you — say "these calls repeat," and add the cache. Interviewers score that derivation higher than a memorized table, because it shows the mechanism rather than the recital.
Watch it happen. The tree below is the real call tree of ways(n). Toggle the memo and every subtree whose question was already answered folds into a single cache-hit lookup.
Memoization fills the cache in whatever order the recursion stumbles into. But once you know all the states — here, amounts 0..n — you can skip the recursion entirely: allocate an array, plant the base cases, and fill it in dependency order, smallest state first, so that by the time you compute dp[i], everything it reads is already sitting there. That's bottom-up DP, or tabulation. Same recurrence, same answers, same O(n) — a loop instead of a call stack.
Which direction should you use? They're interchangeable often enough that the honest answer is "whichever you'll get right under pressure." Top-down is faster to derive and only visits states the problem actually needs. Bottom-up has no recursion-depth ceiling, is usually faster by a constant factor, and — the big one — makes space squeezing visible: if dp[i] only ever reads dp[i−1] and dp[i−2], the array shrinks to two variables and space drops from O(n) to O(1). Climbing Stairs ends life as three lines and two integers. Chapter 21 plays the same trick to squash whole 2-D grids into one row.
A good habit for the room: derive top-down out loud, then say "and if we want, this flips mechanically to a bottom-up loop over amounts 0 to n." You've shown both engines and charged only one derivation.
Here's the actual skill, the one the rest of this chapter drills: the recurrence is a list of the choices available at a state, with the best (or the sum) taken over them. You don't derive it with algebra; you read it off the problem by asking one question: what could the last move have been?
Notice what varies — the choice list and the combiner (+, max, min, "any true") — and what never does: state, choices, smaller states, base case. The question flavor tells you the combiner: "how many ways" sums, "minimum/maximum cost" takes min/max, "can you" takes a boolean OR. Same skeleton, four combiners, most of the DP bank.
House Robber Medium: houses in a row hold loot; alarms trip if you rob two adjacent houses; maximize the haul. Ask the question: at the last house, did you rob it? If yes, you were forced to skip house i−1, so you add v[i] to the best over the first i−2. If no, you keep the best over the first i−1. State: dp[i] = best loot using houses 0..i. Recurrence: dp[i] = max(dp[i−1], dp[i−2] + v[i]). One pass, O(n) time — and since each cell reads only two neighbors, O(1) space after the squeeze.
This shape — take it with a gap, or leave it — is everywhere once you can see it. Run the ledger below: each cell shows which arm of the max won, and the traceback at the end walks the winning arms backward to reveal exactly which houses got hit.
Coin Change Medium: given coin denominations and an amount, return the fewest coins that make it, or −1 if you can't. Chapter 19 showed greedy face-planting here: with coins [1, 3, 4] and amount 6, biggest-first grabs a 4 and limps home with 4+1+1 — three coins — while 3+3 does it in two. Greedy's sin is commitment: once it takes the 4, it can never un-take it.
DP refuses to commit. Ask the question: what was the last coin? It was some c in the coin set, and before it you had made amount a−c as cheaply as possible. So dp[a] = 1 + min(dp[a−c]) over every coin c ≤ a, with dp[0] = 0 and unreachable amounts held at ∞. Bottom-up, that's a table over amounts 0..A filled left to right — O(A·k) for k coins, glossed: one min-over-coins per cell, A cells. Every cell considers all last-coin options, which is precisely the reconsideration greedy skipped.
The table below runs it live, remembering which coin won each cell. Fill it for the nemesis coin set and watch dp[6] come out 2 while the greedy stat sulks at 3 — then trace the winning coins back from the answer.
Two more members prove the skeleton generalizes past "look back one or two cells."
Longest Increasing Subsequence Medium: longest strictly increasing subsequence — elements in order, not necessarily adjacent. State: dp[i] = length of the best increasing subsequence ending exactly at i. Choice: which element came before me? Any j < i with nums[j] < nums[i] — so dp[i] = 1 + max(dp[j]) over those j, and the final answer is the max over all cells, not the last one — a classic off-by-one-thought trap. Cost: O(n²) — each cell scans its whole prefix. (There's a slicker O(n log n) version that binary-searches a pile of "best tails" — Chapter 9's pattern moonlighting inside this one. Offer it as a follow-up, not an opener.)
Word Break Medium: can string s be segmented into dictionary words? State: dp[i] = "the first i characters are buildable." Choice: what was the last word? Any dictionary word w that ends at i with dp[i−len(w)] true. Combiner: boolean OR — this is the "can you" flavor from Section 4. Notice both problems needed a sharper state than "best so far": LIS pins the subsequence's endpoint; Word Break tracks a prefix. Choosing state phrasing that makes the choice list expressible is most of the craft.
Pulling the chapter together, DP announces itself three ways. The question flavor: "how many ways", "minimum/maximum cost", "longest such that", "can you reach" — counting, optimizing, or feasibility over a sequence of interacting choices. The vocabulary: "subsequence", "non-adjacent", "you may take 1 or 2", "or −1 if impossible". The failed alternatives: greedy needs a proof you can't produce (Chapter 19), and plain backtracking (Chapter 18) would revisit the same states exponentially often. In fact that's the cleanest boundary with Chapter 18: if the problem wants every solution listed, you must backtrack — there can be exponentially many. If it only wants a count or a best, listing is waste; collapse the repeats with a memo. Constraints corroborate: n up to ~10³–10⁴ smells like O(n²) DP; a target amount in the thousands smells like a table over amounts (Chapter 3's budget arithmetic).
Then execute the same six moves every time. This skeleton is deliberately engine-agnostic — steps 1–4 are the derivation, and either engine finishes from there.
The pattern, as a whiteboard skeleton:
The flagship is Coin Change Medium, solved both ways from the single recurrence best(a) = 1 + min(best(a−c)). Read the two functions as the same machine with different starters: top-down is the brute recursion you'd derive live, with the memo bolted on in one line; bottom-up is the identical arithmetic with the call stack traded for a left-to-right loop. In the room, derive the first, offer the second — that order shows the mechanism and the engineering judgment.
Details worth narrating: dp[0] = 0 is the whole base case ("zero coins make zero"); unreachable amounts ride along as ∞ and become −1 only at the exit; and in a fixed-width-integer language the ∞ needs headroom so ∞ + 1 doesn't wrap negative — the Scala pane handles it, and mentioning it is free verification signal.