Dynamic Programming Foundations

11 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

The Problem DP Solves: Repeated Work

Dynamic Programming exists because naive recursion often solves the SAME subproblem again and again. Watch fib(5) explode: fib(3) is computed twice, fib(2) three times. At fib(50), the doubling makes ~2⁵⁰ calls. Centuries of work for an answer with 11 digits.

fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# correct, and O(2^n):
# fib(3) computed twice, fib(2) three times,
# and it only gets worse as n grows

Watch fib(5) waste its own time

Fibonacci is the perfect microscope for seeing what DP fixes. The definition is innocent: fib(n) = fib(n−1) + fib(n−2), with fib(0)=0 and fib(1)=1. Ask for fib(5) and recursion does exactly what it's told: fib(5) needs fib(4) and fib(3). fib(4) needs fib(3) and fib(2). Wait: fib(3) again? It was already needed by fib(5) directly. The computer doesn't notice. It happily recomputes fib(3) from scratch, including everything underneath it.

Count the damage across the whole run: fib(3) is computed 2 times, fib(2) 3 times, fib(1) 5 times, fib(0) 3 times, 15 function calls to produce the single number 5. Every gray node in the picture below is a repeat performance of work already done somewhere else in the tree.

The cost curve: from milliseconds to centuries

Here's the frightening part: each +1 on n roughly DOUBLES the number of calls, because every call spawns two children until it hits the floor. n = 5 costs 15 calls. n = 10 costs 177. n = 30 costs about 2.7 million. n = 50 costs around 2⁵⁰ ≈ a quadrillion calls. A modern laptop would grind for decades on a number that fits in 11 digits.

Now the observation that unlocks everything: fib(3) is 2. It was 2 the first time we computed it, it will be 2 the millionth time. The inputs never change, so the answers never change. Recomputing them is like re-deriving the multiplication table in the middle of every exam.

The naive code: perfectly correct, completely doomed

Here is the code causing all that damage. Read it carefully: there is no bug. It returns the right answer every single time. The problem is not correctness. It's the SHAPE of the computation: two recursive calls per level, nothing remembered between them.

This matters because your first instinct on a new problem should still be to WRITE this naive version. It proves you understand the recurrence. DP is never a different algorithm: it's this exact algorithm plus a memory.

Cure #1, Memoization: the notebook (top-down)

Memoization keeps the recursion but adds a notebook (a dict or array). The rule has two halves. BEFORE computing: check the notebook. If fib(3) is already written down, return it instantly, no recursion. AFTER computing: write the answer down before returning it.

Trace fib(5) again with the notebook: fib(5) → fib(4) → fib(3) → fib(2) → fib(1)=1, fib(0)=0 → memo[2]=1 → fib(1) again? …that one's a base case → memo[3]=2. Now fib(4) needs fib(2), LOOKUP, it's 1, no recursion. memo[4]=3. Finally fib(5) needs fib(3), LOOKUP, 2. Answer: 5. Every value was computed exactly once: 9 calls instead of 15, and the gap explodes as n grows. N = 50 drops from a quadrillion calls to 99.

Cure #2, Tabulation: fill the table in order (bottom-up)

Tabulation drops recursion entirely. Instead of starting at fib(5) and diving down, start at the floor and build UP: write down fib(0)=0 and fib(1)=1, then compute fib(2) from them, then fib(3), then fib(4), then fib(5), a single left-to-right loop. By the time any entry is computed, the two entries it needs are already sitting in the table.

And one more gift: look at what the loop actually READS, only the previous two cells. The rest of the table is dead weight. Keep two variables, slide them forward, and space drops from O(n) to O(1). This 'keep only what you still need' trick is called space optimization, and it works on many DP problems.

Memoization vs Tabulation: same medicine, two deliveries

Both cures enforce the same law: each subproblem is solved once. The difference is delivery. Memoization is ON-DEMAND: it only ever computes states the original question actually needs, and the code looks exactly like the naive recursion plus three lines. Tabulation is SYSTEMATIC: it computes every state up to n in a fixed order, trades the recursion stack for a loop (no stack-overflow risk), and usually runs a constant factor faster.

A practical rule for beginners: derive the recurrence naively, memoize it to get correct-and-fast with minimal changes, and rewrite as a table when the order of filling is easy to see (like counting up 1, 2, 3, …). Most of this course's DP lessons teach exactly that journey.

When Does DP Apply?

DP needs two ingredients. (1) OVERLAPPING SUBPROBLEMS: the recursion meets the same smaller problem repeatedly (fib does; merge-sort doesn't, its halves never overlap). (2) OPTIMAL SUBSTRUCTURE: the best answer to the big problem is built from best answers to smaller ones.

# the two-ingredient DP test:

# 1. do subproblems REPEAT?
fib(5) -> fib(3) twice         YES -> DP helps
mergesort -> two fresh halves  NO  -> not DP

# 2. do best small answers build the big one?
best_route(D) uses best_route(C)    YES

The property, defined precisely

'Overlapping subproblems' has an exact meaning: while solving the big problem, the recursion gets handed the SAME smaller problem (same function, same arguments) more than once. Not similar problems. Identical ones, which must therefore have identical answers. The previous concept showed you the disease at a glance; this page teaches you to measure it, and to check for the second ingredient DP needs.

The measurement that matters is the gap between two numbers: how many CALLS the recursion makes versus how many DISTINCT questions it ever asks. fib(6) makes 25 calls but only ever asks 7 different questions, fib(0) through fib(6). The other 18 calls recompute known answers. When that gap is huge, a cache turns the repeats into free lookups, and that is the entire business model of DP.

Put a counter on fib(6) and tally every repeat

Don't take the overlap on faith, instrument the code. Hang a counter on the naive function so every call tallies its argument, then run fib(6) once and read the receipts.

The tally: fib(5) runs once, fib(4) twice, fib(3) three times, fib(2) five times, fib(1) eight times and fib(0) five times, 25 calls to compute the single number 8. Look closer at the repeat counts for fib(6) down to fib(1): 1, 1, 2, 3, 5, 8. The waste itself grows as a Fibonacci sequence: each level down, duplicates breed more duplicates. That is why the pain is exponential rather than a modest overhead: fib(10) already makes 177 calls for 11 distinct questions, and fib(50) would make about 40.7 billion calls for 51.

The scoreboard: 25 calls, 7 distinct questions

Here is the whole run compressed into a scoreboard. Seven distinct subproblems carry all the information; the remaining 18 calls are reruns of answers already known somewhere in the tree. A notebook with seven slots would have collapsed fib(6) to seven computations plus a handful of lookups. Exactly what the next two concepts build.

Merge sort recurses too, so why isn't it DP?

Recursion alone does not create overlap. Merge sort on an 8-element array splits the slice [0..7] into [0..3] and [4..7], then splits those again. Run the same counter experiment on it: 15 calls, 15 DISTINCT slices, zero repeats. Every subarray is solved exactly once, because the two halves share no elements. The pieces are disjoint by construction.

That is why merge sort is filed under divide and conquer, not DP. A memo would be dead weight there: every key would be written once and never read again. Caching only pays when different branches of the recursion funnel into the SAME subproblem, the way fib(5) and fib(4) both funnel into fib(3).

Ingredient two: optimal substructure

Overlap alone isn't enough. DP also needs optimal substructure: the best answer to the big problem must be buildable from the best answers to its subproblems. In one plain sentence with an example. The cheapest way to reach step 10 in Min Cost Climbing Stairs extends the cheapest way to reach step 8 or step 9, because swapping in a pricier route to step 8 could only make things worse. When that sentence holds, you can trust small answers while assembling big ones and never revisit them.

A counter-example proves it's a real filter: the LONGEST simple path in a graph does not have it. Gluing the longest path TO some node onto the longest path FROM it can revisit vertices, so best pieces don't combine into a legal best whole, and indeed no simple per-node table solves that problem.

The two-question test you'll run before every DP problem

From now on, interrogate every candidate problem with this pair. Question 1: does my brute force ask the same question twice? Exhibit one concrete repeat, like fib(3) appearing twice inside fib(5), or instrument a counter and compare calls against distinct arguments. Question 2: can I say, in one sentence, why the best answer is built from best sub-answers? Two yeses and DP applies; the next concepts turn that yes into code. You'll run the test for real in Climbing Stairs, House Robber and Coin Change, where the repeats hide behind stories instead of a formula.

Memoization: Top-Down DP

Memoization keeps your recursive thinking and adds a notebook (a dict/array). Before computing, check the notebook; after computing, write the answer in. Every subproblem is solved exactly once: fib collapses from O(2ⁿ) to O(n) with three added lines.

memo = {}

f(n):
    if n in memo: return memo[n]   # check FIRST
    if n <= 1: return n            # base case
    memo[n] = f(n-1) + f(n-2)      # store AFTER
    return memo[n]

The notebook law: two rules, zero exceptions

The first concept sold you the notebook idea at a glance. Here is the fine print: a contract with exactly two clauses. Rule 1: CHECK before you compute. The first thing a call does is ask 'is my answer already written down?'. If yes, return it immediately, zero recursion. Rule 2: WRITE before you return. The last thing a computing call does is record its answer under its arguments.

Every memoized solution you will ever write is these two rules wrapped around an ordinary recursion. Break rule 1 and the notebook is never read. Break rule 2 and it is never written. Both breakages still return correct answers, only slowly, which is why this page ends with the two bugs and how to spot them.

All nine calls of memoized fib(5), one by one

Naive fib(5) makes 15 calls. Add the notebook and count again: exactly 9, each classifiable. Four calls do real work: fib(5), fib(4), fib(3), fib(2) each compute their sum once and write it down. Three calls hit the base-case floor. Fib(1) twice and fib(0) once return their definition, no notebook involved. Two calls are pure lookups: when fib(4) needs fib(2) for its second branch, the notebook already says 1; when fib(5) needs fib(3), it says 2.

Follow the numbered order below and notice WHERE the lookups happen: always on the second branch of a call, after the first branch already filled the notebook underneath. The left side of the call tree does the work; the right side reaps it.

The three added lines, pointed at

Here is the memoized code. Three additions and nothing else: the first line creates the notebook; the 'if n in memo' pair at the top of the function is Rule 1 (check before anything); the 'memo[n] = ...' assignment is Rule 2, compute, store, and only then return the stored value. The recurrence itself, fib(n−1) + fib(n−2), is untouched: memoization is a wrapper around your thinking, not a replacement for it.

One detail deserves a spotlight: the memo key is exactly the function's parameter. That is not a coincidence. The key IS the state: the thing the state-and-transition concept teaches you to design. A function of two parameters would key the notebook by the pair.

Pitfall #1: the shared default notebook

Python tempts you to write the notebook as a default argument: def fib(n, memo={}). It runs, but Python evaluates that {} once, at definition time, so every call in the whole program shares one dictionary. For plain fib that's an accidental speed boost. The moment the answer depends on anything besides the key, the shared notebook serves stale answers.

Concrete failure: a min_coins(amount, coins, memo={}) helper. Ask min_coins(8, coins={1,5}) and it correctly answers 4, caching memo[8]=4 along the way. Now ask min_coins(8, coins={4,6}). The true answer is 2 (4+4), but the shared notebook sees amount 8, finds the old 4, and returns it. Wrong answer, no crash, no warning. The fix: create the notebook per top-level call and let an inner helper recurse.

Pitfall #2: computing but forgetting to WRITE

The sneakier bug: you check the notebook but end the function with 'return fib(n-1) + fib(n-2)', computing the sum without storing it. The notebook stays empty forever, every check misses, and you are back to the full exponential blow-up. The output is still CORRECT, which is what makes this bug evil: no test fails, only the clock does. Measured on fib(20): the forgetful version makes 21,891 calls, identical to having no memo at all, while write-then-return makes 39.

Train the habit: the write and the return should touch the same expression. memo[n] = ...; return memo[n]. If your return line contains a recursive call, Rule 2 is broken.

Reading the finished notebook, and where you'll use it

After fib(5) returns, the notebook holds {2: 1, 3: 2, 4: 3, 5: 5}. Notice what is NOT there: 0 and 1. Base cases return before reaching the write line, so they never take a slot, normal and fine. Each entry was written exactly once; in bushier problems single entries get read dozens of times, and that write-once-read-many ratio is where all the speed comes from.

Memoization is the first tool you'll reach for in every DP lesson ahead: Fibonacci Number, Climbing Stairs and House Robber all memoize the naive recursion before flipping it into a table. Python's functools.lru_cache can enforce the two rules for you: earn it by writing them by hand first.

Tabulation: Bottom-Up DP

Tabulation flips the direction: instead of starting from the big question and recursing down, start from the BASE CASES and build UP with a loop, filling a table until the answer appears at the end. No recursion, no call stack: just an array and a for-loop.

f(n):
    dp = array of size n+1
    dp[0], dp[1] = 0, 1            # seed the bases
    for i in 2 .. n:
        dp[i] = dp[i-1] + dp[i-2]  # build UP
    return dp[n]

One rule rules the loop: never read an empty cell

Memoization gets ordering for free: recursion dives until it hits ground, so by the time any call adds two sub-answers, both exist. Tabulation throws recursion away, which means YOU must supply the order. The whole craft is one sentence: by the time the loop computes a cell, every cell it reads must already be filled. The first concept showed the finished fib table; this page is about why the loop's DIRECTION is the load-bearing part.

Think of each dp cell as a dish with ingredients. dp[i] = dp[i−1] + dp[i−2] declares two ingredients, both to the LEFT of i. A left-to-right sweep therefore cooks every dish after its ingredients are ready. A right-to-left sweep cooks with raw ingredients. You will watch that fail below, with real numbers.

Fill fib(5) left to right, checking ingredients at every step

Seed the bases first: dp[0] = 0 and dp[1] = 1, the only entries that need no ingredients. Now sweep. dp[2] reads dp[1]=1 and dp[0]=0, both filled → 1. dp[3] reads dp[2]=1 and dp[1]=1 → 2. dp[4] reads dp[3]=2 and dp[2]=1 → 3. dp[5] reads dp[4]=3 and dp[3]=2 → 5. Four read-then-write steps, and not once did the loop touch an empty slot. That invariant: ingredients always behind the write. Is the entire correctness argument of bottom-up DP.

The code: four moves

The loop below is the trace you just did, in four moves. Move 1: size the table by the state space, one slot per subproblem, n+1 of them. Move 2: seed the base cases. Move 3: sweep in dependency order. Move 4: return the slot that holds the original question. Every tabulated solution in this track is these four moves with different blanks filled in.

Watch the wrong order fail, cell by cell

Flip move 3. Loop i from 5 down to 2, and run it honestly. dp[5] = dp[4] + dp[3] = 0 + 0 = 0, because both cells are still virgin zeros. dp[4] = 0 + 0 = 0. dp[3] = dp[2] + dp[1] = 0 + 1 = 1. Wrong too (fib(3) is 2), since dp[2] hadn't been computed yet. dp[2] = dp[1] + dp[0] = 1, correct only because its ingredients happen to be the seeds. Final table: [0, 1, 1, 1, 0, 0]. The function returns dp[5] = 0 instead of 5.

Notice the failure mode: no crash, no exception, just quietly reading zeros that were never real answers. This is tabulation's signature bug, and it always traces back to an illegal order. Which is why you check the order BEFORE running, not after.

Finding the legal order in any problem

The general recipe: base cases first, then order the states so every state comes after everything its transition reads. For 1-D transitions that look backward (dp[i−1], dp[i−2]) that means plain left to right. Suffix-style recurrences that read dp[i+1] sweep right to left instead. 2-D tables that read up and left fill row by row, top to bottom. You'll do exactly that in the 2-D concept. And occasionally the legal order is the surprising one: 0/1 knapsack updates a reused row from HIGH sums to LOW precisely so every read lands on an old value, the space-optimization concept shows why.

Memoization vs Tabulation

Both cure repeated work; each subproblem is solved once either way. Memoization keeps recursive thinking and only computes subproblems that are actually NEEDED. Tabulation trades recursion for a loop. No stack limits, faster constants, and it sets up the space optimizations coming next.

# MEMOIZATION              TABULATION
# recursion + notebook     loop + table
# starts at the TOP        starts at the BASES
# computes what's needed   computes everything
# recursion depth limits   no recursion at all

# same answers, same O(n): two directions

A buyer's guide, not a rematch

You have now built both deliveries: the notebook and the table. The first concept gave the one-line summary (same medicine, two deliveries) so this page is the working comparison you'll actually shop with: five dimensions where they genuinely differ, a worked example where the two compute DIFFERENT amounts of work, a crash you can reproduce, and a ten-second decision rule.

Five dimensions that actually differ

Time complexity ties on most problems: both solve each needed state once. The differences live in operations. Code shape decides how you think: recursion mirrors the recurrence you derived; the loop mirrors the fill order you chose. Coverage decides how much work happens: the notebook computes only states that are actually asked; the table fills its whole range. Stack risk decides whether big inputs crash. Constants decide tight time limits. Ease of space optimization decides memory.

Two of those rows deserve hard numbers, so the next two sections deliver them: coverage (a race the notebook wins by half) and stack risk (a three-line crash).

A race the notebook wins: coins {4, 6}, amount 20

Fewest coins for amount 20 using coins {4, 6}. Tabulation must fill dp[0..20]: all 21 cells, each scanned against both coins, including every odd amount. Memoization starts at 20 and only follows real subtractions: 20 asks about 16 and 14; those ask about 12, 10 and 8; the frontier continues through 6, 4, 2 and 0. Total touched: 10 amounts. The other 11: every odd amount, plus 18. Are never visited, because no chain of −4/−6 steps from 20 reaches them.

Both return 4 (6+6+4+4). The memo ends holding {4:1, 6:1, 8:2, 10:2, 12:2, 14:3, 16:3, 20:4} plus one recorded dead end, ∞ at amount 2. The table additionally computes answers nobody asked for, like dp[18] = 3. On this toy the notebook skipped 52% of the state space; on genuinely sparse spaces (huge amounts with coarse coins, interval and digit DP) laziness can skip almost everything.

The two shells, side by side

Read these as templates, not as fib code. The memo shell is your naive recursion with the two notebook rules stitched in. The tab shell is seeds plus one sweep. The correspondence is exact: memo's base case becomes the table's seed, each recursive call becomes a read of an earlier slot, and the call order becomes the loop order. Translating top-down into bottom-up is a mechanical rewrite along those three arrows: you'll perform it in every DP lesson.

Stack risk and constants: the operational tiebreakers

Python's default recursion limit is 1000 frames, and memoized fib dives n frames deep before unwinding. So memoized fib(1500) dies with RecursionError before finishing any arithmetic, three lines to reproduce. The loop computes fib(1500), a 314-digit number, without blinking. Deep chain-shaped state spaces: n in the hundreds of thousands, long strings, are tabulation territory, full stop.

Constants matter too: each memo state pays a function call plus a dict probe; each table state pays one array read and write. Same O(n), but the loop usually wins by a visible constant factor: rarely a complexity story, often a time-limit story.

The ten-second decision rule

Neither is 'better', they trade laziness against safety. Here is the rule this track uses and drills on every DP problem ahead, always in the same order: think top-down, ship bottom-up.

The DP Framework: State → Transition → Base

Every DP solution answers three questions. STATE: what parameters describe a subproblem? (dp[i] = ...what, exactly?) TRANSITION: how does a state combine smaller states? (the recurrence) BASE: which tiny states are known outright? Answer these three and the code writes itself.

# the 3-question template (climbing stairs):

STATE:       dp[i] = ways to reach step i
TRANSITION:  dp[i] = dp[i-1] + dp[i-2]
BASES:       dp[0] = 1,  dp[1] = 1
ANSWER:      dp[n]

State = the minimal info that makes the future computable

This is the core skill of DP: the one that separates knowing the technique from solving new problems cold. Memorize the definition: a state is the MINIMAL information about your situation that makes the rest of the problem computable. Stand in the middle of the problem and ask, 'what must I know to finish optimally from here?' Whatever answers that question is the state; everything else is history that no longer matters.

Test it on Climbing Stairs: you are somewhere on the staircase. Does the exact path that got you here change the number of ways to finish? No, from step i, the remaining options depend only on i. One number summarizes the entire past. That collapse: a huge choice history compressing into a tiny summary. Is why DP tables stay small while choice trees explode.

Three problems, three states

House Robber's state is also a single index, dp[i] = the best loot from houses 0..i, but with a wrinkle worth naming: the rob-or-skip tension does NOT need its own parameter. The transition resolves it by proposing both futures and taking the max; some solutions equivalently carry two running values (best-if-robbed, best-if-skipped). Either way the choice is folded into VALUES, not into an extra state dimension.

Coin Change flips the axis entirely: the state is not a position in any list, it is the REMAINING AMOUNT. dp[a] = fewest coins that make amount a. From amount 27, the future depends only on the 27. Never on which coins built the part you've already paid. One number again, completely different meaning: the state is whatever the future needs, not whatever the input looks like.

Transition = split on the LAST choice

Once the state has a name, derive the transition with one move: enumerate what the LAST choice could have been. Stairs: the final hop was 1 or 2, so dp[i] = dp[i−1] + dp[i−2]. A counting question ADDS its branches. Robber: the last decision, at house i, was rob or skip, so dp[i] = max(dp[i−1], dp[i−2] + loot[i]), a best question MAXES its branches. Coin Change with coins {1, 2, 5}: the last coin paid was one of the three, so dp[a] = 1 + min(dp[a−1], dp[a−2], dp[a−5]), a fewest question MINS its branches (dp[11] = 3, via 5+5+1).

Why the last choice and not the first? Because removing the last choice leaves a smaller version of the SAME question, 'ways to reach step i−1', which is exactly what your table stores. Splitting on the first choice leaves 'ways to finish from step 1 upward', a different question your table doesn't hold.

The pitfall: a bloated state

The classic beginner bug is dragging history into the parameters. Watch it on House Robber: best(i, money_so_far), 'I'm at house i, having already collected X.' It recurses correctly, but the keys explode: on the five-house street [2, 7, 9, 3, 1], that formulation produces 25 distinct (i, money) pairs, where the lean state has 7 distinct values of i. Worse, a cache hit now requires BOTH numbers to match, so the overlap that makes DP pay nearly disappears. The memo pays rent and does nothing.

The shrink test is the definition itself: does the FUTURE depend on it? money_so_far doesn't change what is collectible ahead: it's a running output, not a constraint. So move it out of the parameters and into the return value: best(i) returns the most collectible from house i onward. Rule of thumb: a parameter that only records the past, without restricting future options, belongs in the return value, not in the state.

How to know you got it right

Run these checks at design time, where fixes cost nothing. They catch the vast majority of broken DP before a single line of code exists. A fuzzy state or a leaky case-split is much easier to repair in a sentence than in a loop.

Where this skill gets drilled next

The next two concepts are this skill specialized by shape: 1-D, where the state is a single index or amount (you'll walk House Robber's whole row), and 2-D, where one number stops being enough, grids and pairs of strings. After that, every lesson in the track opens with the same two moves you just practiced: say the state sentence, split on the last choice. Get those two right and the code is transcription.

1D DP: Decisions Along a Line

The most common DP shape: states line up along one axis (steps, houses, days, amounts), and dp[i] depends on a few earlier entries. The transition usually encodes a DECISION (take it or skip it, extend or restart) evaluated with max/min/sum.

# house robber: one decision per house
dp[i] = max(dp[i-1],              # skip house i
            dp[i-2] + loot[i])    # rob house i

dp[0] = loot[0]
dp[1] = max(loot[0], loot[1])
answer = dp[last]

The shape: states on a line

1-D DP is the workhorse shape: the entire situation compresses to ONE number that moves along a line, a step index, a house index, a day, a remaining amount. The table is a single row, the transition reaches back a constant distance, and the sweep runs left to right. Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs, House Robber, Decode Ways and Coin Change all live here.

The recognition cue: as choices are made, does exactly one 'position' advance? If describing your situation honestly needs just that one number, per the state test from the previous concept, you have a 1-D problem, and the design collapses to two questions: what does dp[i] mean, and which earlier cells feed it?

Walk House Robber's whole row: [2, 7, 9, 3, 1]

State sentence first: dp[i] = the maximum loot obtainable from houses 0..i, rob house i or not. Bases: dp[0] = 2 (only one house exists) and dp[1] = max(2, 7) = 7 (the first two are adjacent, pick the richer). Every later cell weighs the same two candidates. SKIP house i and keep dp[i−1], or TAKE house i for dp[i−2] + loot[i], since its neighbor is then off-limits.

Cell by cell: dp[2] = max(skip 7, take 2+9 = 11) = 11. Take; pairing house 2 with house 0 beats clinging to house 1. dp[3] = max(skip 11, take 7+3 = 10) = 11. Skip; house 3's three coins can't compete. dp[4] = max(skip 11, take 11+1 = 12) = 12. Take, building on dp[2]'s 11. Answer: 12, from robbing houses 0, 2 and 4.

Two cells worth a second look

dp[3] = 11 chose SKIP: 7 + 3 = 10 cannot beat the 11 already banked in dp[2]. The row automatically resists a tempting-but-bad house. No special-case code, the max does it. dp[4] = 12 chose TAKE, and look at WHICH past it built on: dp[2] = 11 is itself the house-0-plus-house-2 combination, so the final plan reads 2 + 9 + 1 across houses 0, 2, 4. Nobody planned that combination; it emerged because each cell stored the best of its prefix and later cells trusted it blindly. That trust is optimal substructure doing its job.

The 1-D skeleton every problem shares

Strip the story and one skeleton remains: size the row by the state space, seed the smallest cases, sweep once, combine a constant number of look-backs per cell. Adapting it to a new problem means changing three blanks. What dp[i] MEANS, which cells feed it, and whether the combiner is +, max or min.

Coin Change stretches the same skeleton two ways without leaving 1-D: the row is indexed by AMOUNT (size amount+1, seeded with dp[0] = 0), and each cell scans every coin instead of exactly two look-backs. Still one state variable: the inner scan is just a wider combiner.

Recognizing 1-D in the wild

Two questions sort almost everything. One: does a single position or quantity advance as choices are made? Two: does the answer at position i depend on a fixed few earlier positions, or a scan over them? Two yeses: draw one row and start filling. Contrast the case that fails the test: comparing two strings advances TWO positions independently, and no single number captures both. That is the next concept's territory.

2D DP: Grids and Pairs of Sequences

When ONE index can't describe a subproblem, use two. dp[r][c] = answer for a grid cell (paths, costs); dp[i][j] = answer for a PAIR of prefixes (comparing two strings). The framework is unchanged: only the table gains a dimension.

# unique paths: the state needs TWO indexes
dp[r][c] = dp[r-1][c] + dp[r][c-1]
#            from above    from the left

# bases:  first row = 1, first column = 1
# answer: dp[last row][last column]

When one number can't say where you are

'I'm at step 7' fully describes your situation on a staircase. Say 'I'm at 7' on a grid and the reply is 'which row?'. Some situations need TWO numbers before the future becomes computable: a robot needs (row, column); comparing two strings needs (how much of A is consumed, how much of B). The state discipline is unchanged, minimal info that makes the future computable, there is simply one more coordinate, and the row of answers becomes a grid of answers.

Two families dominate: GRID problems, where the state is literally a cell (Unique Paths), and TWO-SEQUENCE problems, where the state is a pair of prefix lengths (Longest Common Subsequence, Edit Distance). Both are ahead as full lessons; here you'll build one small table of each kind by hand.

Build the 3×4 Unique Paths table, corner by corner

A robot walks from the top-left of a 3×4 grid to the bottom-right, moving only right or down. State: dp[r][c] = the number of ways to reach cell (r, c). Last-choice split, exactly as in 1-D: the final move into (r, c) was DOWN (from above) or RIGHT (from the left), so dp[r][c] = dp[r−1][c] + dp[r][c−1]. Bases sit on the edges: one straight-line route to each cell of the top row and of the first column.

Now the six interior cells, row by row: dp[1][1] = 1+1 = 2. dp[1][2] = 1+2 = 3. dp[1][3] = 1+3 = 4. Next row: dp[2][1] = 2+1 = 3, dp[2][2] = 3+3 = 6, dp[2][3] = 4+6 = 10. Ten routes across the little grid, and every one of those additions read two cells that were already final.

Why row-by-row is a legal order

The transition reads UP (r−1, same column) and LEFT (same row, c−1). Sweep rows top to bottom and each row left to right: when (r, c) computes, its up-neighbor finished in the previous row and its left-neighbor finished moments ago in this row. The tabulation rule, never read an empty cell, holds at every single step. Column-by-column would be equally legal here, and so would diagonals; row-major is simply the order two nested for-loops give you for free.

The 2-D skeleton

Memorize the shape, not the numbers: allocate R×C, seed the edges, two nested loops, read up/left, answer in the far corner. Variations swap only single lines: an obstacle grid zeroes blocked cells, a min-path-cost grid replaces + with min plus the cell's own cost. The frame never moves.

Two strings and the +1 padding trick

The other family. For the Longest Common Subsequence of A = 'ab' and B = 'cab', define dp[i][j] = the LCS length of the FIRST i characters of A and the FIRST j characters of B. Lengths, not indexes: i = 0 means 'none of A', so row 0 and column 0 are a free base case of zeros, nothing overlaps with an empty string. That is the +1 padding trick: a (len(A)+1) × (len(B)+1) table whose zeroth row and column absorb the bases.

Padding's price is a translation you must never fumble: cell (i, j) talks about characters A[i−1] and B[j−1]. Fill the 3×4 table: 'a' vs 'c' shares nothing → 0; 'a' vs 'ca' matches on 'a' → 1; the 'ab' row ends at dp[2][3] = dp[1][2] + 1 = 2 because 'b' matches B's last character. Write A[i] where A[i−1] belongs and every comparison shifts one character: the classic 2-D off-by-one, usually announced by an IndexError on the final row.

Recognition cues and what's ahead

The tell for 2-D is two independent movers: a position needing two coordinates, two prefixes advancing at their own pace, or an item-index paired with a remaining capacity. When you spot it, say the two-part state sentence aloud, seed the edges, and sweep row-major. Then notice one more thing about every table on this page: each cell read only the PREVIOUS row and its own. Which is a memory trick waiting to happen, and it's the next concept.

Space Optimization: Rolling Variables

Look at fib's transition: dp[i] uses ONLY dp[i−1] and dp[i−2]. The rest of the table is dead weight kept alive for nothing. Keep just two variables and roll them forward: O(n) space becomes O(1). 2D tables that only read the previous row shrink to one row the same way.

# transition reaches back 2  ->  keep 2 variables
prev2, prev1 = base0, base1

for i in 2 .. n:
    cur = combine(prev1, prev2)
    prev2, prev1 = prev1, cur     # roll forward!

return prev1

Audit what the loop actually reads

A finished table is a receipt: it shows exactly which cells each step READ. Audit fib's loop: dp[i] touches dp[i−1] and dp[i−2], never dp[i−3], never dp[0]. At any moment only a two-cell window of the array is live; everything left of it is a corpse kept in memory out of politeness. For fib of a million, that's a million integers guarding two useful values.

The reach rule follows: if the transition reaches back at most k cells, k variables replace the array. If a 2-D transition reads only the previous row, one row replaces the grid. Time complexity never changes, same additions in the same order, the trick simply stops hoarding dead answers.

Fib: the array becomes two variables

Watch the window slide across fib(5): compute 1+0 = 1, window becomes (1, 1); compute 1+1 = 2, window (1, 2); compute 2+1 = 3, window (2, 3); compute 3+2 = 5, window (3, 5). Answer: 5. Identical additions to the table version, the array just never existed. One trap in the rewrite: prev2 must receive prev1's OLD value. Python's simultaneous assignment handles that in one line; split it into two statements in the wrong order and the window duplicates a value instead of sliding.

Unique Paths: twelve cells become one row

The 3×4 Unique Paths table from the last concept reads up and left. 'Up' is the previous row's value at the SAME column, so keep one row and overwrite it in place. Just before writing row[c], the slot still holds the previous row's value: that IS 'up'. row[c−1] was updated moments ago: that IS 'left'. The whole transition compresses to row[c] += row[c−1].

The row's journey, computed: it starts as the top edge [1, 1, 1, 1]; after sweeping grid-row 1 it reads [1, 2, 3, 4]; after grid-row 2, [1, 3, 6, 10]. Same answer, 10, with 4 integers instead of 12. Picture a window one row tall sliding down the grid. Each pass, the buffer stops impersonating row r−1 and becomes row r.

The pitfall: overwriting a cell you still need

In-place reuse has one deadly failure: reading a slot AFTER this pass already overwrote it. Watch it on 0/1 subset-sum: nums = [3, 4], target 6, each number usable once. dp[s] means 'sum s is makeable'; dp[0] = True. Process the 3 sweeping sums UPWARD: dp[3] |= dp[0] → True; two steps later dp[6] |= dp[3], but that dp[3] was set THIS pass, so the single 3 just got counted twice, and the row proudly claims 6 is makeable. It isn't: subsets of {3, 4} reach only 0, 3, 4 and 7.

Sweep DOWNWARD instead, s = 6, 5, 4, 3: dp[6] |= dp[3] reads the not-yet-updated False, and only dp[3] flips this pass; processing the 4 then flips dp[4] and leaves dp[6] False. Correct. The principle: when the new row overwrites the old one in place, every read must land on an OLD value; iterating sums high-to-low guarantees each dp[s−x] you read is still last round's answer. That is exactly why Partition Equal Subset Sum's inner loop runs backward.

Optimize last: the workflow rule

Space optimization is a refactor, never a starting point. Get the full table correct first, stare at the transition's reach, then shrink. Two reasons: a full table is dramatically easier to debug. You can print it and check any cell by hand, as you did all through this track, and some problems later need the history anyway (reconstructing the actual path or choices requires cells the rolled version already discarded). Correct, then compact.

Recognizing DP in the Wild

DP problems rarely announce themselves. They ask 'how many ways', 'minimum cost', 'longest', 'can you', while hiding choices whose subproblems overlap. Learn the tells: sequential decisions, a shrinking parameter, exponential naive solutions, and answers built from smaller versions of the same question.

# the DP smell test:
'how many ways...'      -> counting DP (sum)
'min cost / max value'  -> optimizing DP (min/max)
'can you reach/split'   -> feasibility DP (or)

# confirm: naive is exponential, but the
# distinct states are few (n, or n x m)

The two-second sniff test

No problem announces 'I am DP'. You get a story, and the tell is in the QUESTION plus the CHOICES. Question shapes: 'how many ways...', 'minimum / fewest...', 'maximum / longest...', 'can you...'. Choice shape: answers are built by a SEQUENCE of small decisions, hop sizes, take-or-skip, which coin next, match-or-delete a character. Both present together? Suspect DP.

Then confirm with arithmetic before committing: the brute force over choice sequences is exponential, but the number of distinct SITUATIONS is small. Partitioning a 20-number set (sum 100) means 2²⁰ = 1,048,576 subsets, yet only 21 × 51 = 1,071 distinct (items considered, target left) situations exist. A million-sized choice tree crammed into a thousand situations must revisit the same situations constantly. That is the calls-versus-distinct gap from the overlap concept, spotted straight from the problem statement.

Four disguises, classified in one line each

Most interview DP wears one of four costumes. Practice producing the classification in one breath. (1) 'A frog at pad 0 hops 1 or 2 pads forward; count the distinct hop sequences to pad n' → a LINE of positions, counting → dp[i] = dp[i−1] + dp[i−2]. (2) 'Houses hold cash, alarms link neighbors, maximize the haul' → TAKE-OR-SKIP along a line → dp[i] = max(dp[i−1], dp[i−2] + v[i]). (3) 'Coins {1, 4, 6}: make 14 with the fewest coins' → an AMOUNT state → dp[a] = 1 + min over coins; answer 3 via 6+4+4, while greedy's 6+6+1+1 spends 4. (4) 'Longest common subsequence of two strings' → TWO SEQUENCES → dp[i][j] over prefix pairs.

Counter-example #1: greedy already wins

'Fewest coins' is not automatically DP. With canonical coin systems (US coins {1, 5, 10, 25}) always grabbing the biggest coin is provably optimal: checked exhaustively, greedy's count equals DP's for every amount from 1 to 500 (67 → 25+25+10+5+1+1, six coins, both methods). Real currencies are designed that way. When a locally-best choice can be argued safe, skip the table: greedy is less code, O(1) space, and faster.

Change the coin set to {1, 5, 11} and the verdict flips: for 15, greedy grabs 11+1+1+1+1 = 5 coins while DP finds 5+5+5 = 3. The recognition skill is not 'coins ⇒ DP'; it is 'try one greedy exchange argument. If a single example breaks it, DP takes the case.' Unstated coin systems in interviews are adversarial: assume greedy breaks.

Counter-example #2: the answer IS the enumeration

DP compresses counts and bests; it cannot compress output. 'How many routes cross an 18×18 grid?' is a 324-cell table whose corner holds C(34,17) = 2,333,606,220. 'PRINT every route' is 2.3 billion lines of output: no table shrinks that, because the routes themselves, not a statistic about them, are the demanded answer. When the required output grows exponentially, DP can help generate it but cannot make the job polynomial.

A subtler impostor: 'longest simple path in a general graph'. It smells like DP: longest! paths!, but optimal substructure fails: the best path to a midpoint may consume vertices the continuation needs, so best pieces don't glue into a legal best whole. The problem is NP-hard; no clean per-node table exists. The two ingredients from the overlap concept are requirements, not decorations.

The pocket detector

Compressed to a card, in the order that saves interview minutes: suspicion is free, confirmation is arithmetic, and the counter-checks stop you from tabulating a greedy problem, or promising a polynomial answer to an exponential demand.

The DP Checklist

Everything assembled into one repeatable procedure: (1) RECOGNIZE the DP smell and confirm overlap + optimal substructure. (2) DEFINE the state as a precise sentence. (3) DERIVE the transition via the last choice. (4) ANCHOR base cases. (5) IMPLEMENT memo-first, then tabulate. (6) OPTIMIZE space if the reach is short.

# before ANY DP problem:
1. RECOGNIZE   count / min-max / can-you + overlap
2. STATE       dp[i] = '...' (a full sentence)
3. TRANSITION  case-split the LAST choice
4. BASES       smallest states, sanity-checked
5. IMPLEMENT   memo first, then table
6. OPTIMIZE    short reach -> rolling variables

Four steps, each with its own pass test

You now own all the pieces: the disease, the two cures, states and transitions, the 1-D and 2-D shapes, the space trick, the detector. This page bolts them into a single procedure: four steps, and, more importantly, a PASS TEST for each. The difference between 'I followed the recipe' and 'it works' is knowing how to check your own work at every step, before the code exists.

Run the steps in order and refuse to advance past a failed test. Most broken DP submissions trace back to a skipped test here: usually a fuzzy state sentence or an unverified base case.

The checklist itself

Step 1's test is concrete: exhibit an actual repeat, the way fib(3) appears twice inside fib(5). If you can't point at one, you may be holding divide-and-conquer, not DP. Step 2's test is the sentence: 'dp[i] = the number of distinct ways to reach step i' passes; 'dp[i] = something about the first i items' fails. Step 3's test is coverage: every way the last move could happen appears in exactly one case. Stairs' last hop is 1 or 2, no third option, no overlap between the cases. Step 4's test is mechanical: bases hand-verified against the sentence, fill order never reading an unfilled cell.

The checklist run on Climbing Stairs, end to end

The four steps produce an eight-line function whose comments ARE the checklist. This artifact shape (sentence, transition, bases, sweep) is what every lesson in this track builds toward, and it is exactly what an interviewer wants to watch appear on the whiteboard, in this order, with the tests spoken as you go.

Pre-flight: three checks before you type

Even with a finished design, spend sixty seconds on pre-flight. One: say the state sentence aloud, verbatim, if it wobbles, re-derive before coding. Two: hand-verify the bases on n = 1 and n = 2 against reality by ENUMERATING: stairs n=1 has one way (a single hop) and n=2 has two (1+1, and 2), so dp[1] = 1 and dp[2] = 2 must match. If your seeds produce 1 or 3 for n=2, the off-by-one dies here instead of inside a judge. Three: check the fill order against the transition's reach, reads behind the write, always.

Three self-checks: answers included

Q1, House Robber on [2, 7, 9, 3, 1]: what is dp[3], and which option won? Work it before reading on. Answer: dp[3] = max(dp[2], dp[1] + 3) = max(11, 10) = 11. SKIP; house 3's three coins can't beat the 11 already banked.

Q2, Climbing Stairs n = 4: the table says 5 ways, name them. Answer: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2. Found only four? You probably merged two orderings of the single 2-hop, counting DP counts SEQUENCES, not sets. Q3, Coin Change with coins {1, 2, 5}, amount 11: state, transition, answer? Answer: dp[a] = fewest coins making a; dp[a] = 1 + min(dp[a−1], dp[a−2], dp[a−5]); dp[11] = 3 via 5+5+1. The full row is below: audit any cell's arithmetic against its three look-backs.

Where you go from here

That is the whole foundation: recognize, name the state, split the last choice, pick a delivery and verify, and only then optimize space. The DP problems ahead, from Fibonacci Number and Climbing Stairs through House Robber, Coin Change, Unique Paths, Word Break and Longest Common Subsequence, are this checklist run again and again with the training wheels coming off gradually. Around the fifth run you'll stop reading the list. That is the point.

All DSA learning paths