The DP archetypes you'll see
📖 Walk me through it — plain English
Dynamic programming (DP) just means: break a big problem into smaller versions of itself, solve each small version once, and reuse the answers instead of recomputing them. The catch is figuring out what the small versions are and how a bigger answer is built from smaller ones — that relationship is called the recurrence (a formula that defines f of a thing in terms of f of smaller things). This lesson's claim is that you almost never invent a recurrence from scratch: most DP problems fall into one of six familiar archetypes (recurring shapes). If you can name the shape, you already know the rough form of the formula.
Think of it like recognizing a recipe by its ingredients. You don't need to memorize ten thousand dishes — once you see "flour, water, yeast, oven," you know you're baking bread and the steps follow. Here the "ingredients" are the inputs: a single array, a grid, items with a weight budget, a range you can split, a set of things to visit, or two strings. Each points to one of the six boxes above. The smallest, most common shape is 1D linear: the answer at position i depends only on the one or two positions just before it, written f(i) = something with f(i-1) and f(i-2). Let's trace that one concretely.
Concrete example: House Robber. You're a thief walking past houses worth [2, 7, 9, 3]. You may rob houses, but never two that sit next to each other (an alarm links neighbors). Maximize the loot. Define f(i) = the most money you can have after deciding about houses 0..i. At each house you face one choice: skip it (keep your best-so-far, which is f(i-1)), or rob it (take its value plus whatever was safe two houses back, f(i-2), since the immediate neighbor is now off-limits). So f(i) = max( f(i-1), house[i] + f(i-2) ) — pure 1D linear shape. We'll fill one cell per house, left to right. The highlighted cell is the one we're computing.
Answer: 11 (rob houses 0 and 2: 2 + 9). Notice what made it easy — each cell looked back only at the previous one or two cells, never recomputed anything, and we swept left to right exactly once. That's why 1D linear DP runs in O(n) time (n cells, constant work each) and can even drop to O(1) extra space, since you only ever need the last two values, not the whole row.
The bigger lesson: the same "name the shape, then the formula falls out" trick applies to all six archetypes. A grid means f(i,j) comes from the cells above and to the left. A knapsack (items + a capacity budget) means f(item, capacity) = best of "skip this item" vs "include it and spend its cost." Two strings means f(i,j) over their prefixes (the first i and first j characters). Same muscle every time: define what f means, ask what one decision you face at each step, and write the bigger answer in terms of the smaller ones you already computed.
Most DP problems are variants of a handful of shapes. Spot the shape, half the work is done.
The vocabulary, defined once
Before the catalogue, pin down the words. Every term below shows up in every DP solution, so it pays to know them cold rather than nod along.
- Dynamic programming — an approach for problems where the best overall answer is assembled from best answers to smaller pieces, and those pieces repeat. You compute each piece once and store it. The name is historical (Richard Bellman, 1950s) and means nothing useful; read it as "smart recursion with a memory."
- Overlapping subproblems — the smaller pieces get asked for more than once. Plain recursion would recompute f(3) dozens of times; DP computes it once and looks it up after. This is the property that makes DP pay off. (Without it, plain divide-and-conquer like mergesort is enough.)
- Optimal substructure — the best answer to the whole is built from best answers to its parts. House Robber has it: the best loot through house i uses the best loot through earlier houses. This is the property that makes DP correct. (Some problems fail this; for those, greedy or search is required instead.)
- State — the set of facts that fully describe one subproblem, written as the arguments to f. In House Robber the state is just one number i (which house). In knapsack it is two numbers (which item, how much capacity left). Choosing the right state is the hard part of DP; everything else is bookkeeping.
- Transition (recurrence) — the formula that builds f(state) from f(smaller states). It almost always reflects a single decision you face: take it or skip it, go right or go down, split here or there.
- Base case — the smallest states whose answer you write down directly with no recurrence (e.g. f(0) = 2, or "an empty string matches an empty pattern"). The recurrence stands on these; forget one and the whole table is wrong or crashes.
- Memoization — top-down DP: write the natural recursion, then cache each result in a dictionary/array so the second request is a lookup. You write the recurrence as-is; the cache removes the overlap.
- Tabulation — bottom-up DP: fill an array from the base cases forward, in an order where every cell's dependencies are already filled. Same answers, no recursion stack, often easier to space-optimize.
Two-property test for "is this DP?" A problem is a DP candidate exactly when it has both overlapping subproblems (the pieces repeat, so caching helps) and optimal substructure (best-of-whole = combine best-of-parts, so caching is correct). If pieces don't repeat, plain recursion is fine. If best-of-whole can't be built from best-of-parts, DP gives wrong answers — reach for greedy or full search instead.
On-ramp: how to recognize which archetype you're in
You rarely have to invent the state — you recognize it from the shape of the input and the kind of decision. Read the problem and ask three quick questions, in order:
- What's the input? One array → 1D linear. A 2D grid or two sequences you align → grid / string. A bag of items plus a budget → knapsack. A range you can cut at a pivot → interval. A small set (n ≤ ~20) you visit in some order → bitmask.
- What single decision repeats? "Include or skip this element" → knapsack/subset. "Step right or down" → grid. "Match these two characters or not" → string. "Where do I split this range?" → interval. "Which unvisited thing do I go to next?" → bitmask.
- What's the smallest set of facts I must remember to make that decision? Those facts are the state. If "where I am" suffices, state is 1D. If "where I am in two things" matters, it's 2D. If "what I've already used up" matters, add it as a dimension.
The grid below is the lookup table for steps one and two; the rest of this lesson gives each row a one-line "smell," a canonical example, and its state/transition so step three writes itself.
Climb stairs · House robber · Max subarray (Kadane).
f(i) depends on f(i-1), f(i-2)
Unique paths · Min path sum · Edit distance.
f(i,j) from f(i-1,j), f(i,j-1), f(i-1,j-1)
0/1 (subset sum) · Unbounded (coin change).
f(i, capacity) — include or skip item i
Matrix chain · Burst balloons.
f(i,j) splits over k in (i,j)
TSP-style, n ≤ 20.
f(mask, i) = best ending at i, visited = mask
LCS · Palindromes · Regex matching.
f(i,j) over two prefixes
The six archetypes, one at a time
For each shape: the smell (the cue in the problem statement that points here), a canonical example, and the state / transition / base case spelled out. Memorize the smells; the formulas follow from them.
1 · 1D linear
Smell: one array or one position-index, and the answer at i depends only on a constant number of earlier positions.
Canonical example: Climbing Stairs — count the ways to climb n steps taking 1 or 2 at a time.
State: f(i) = answer considering positions up to i. Transition: f(i) = f(i-1) + f(i-2) (the last move was a 1-step or a 2-step). Base: f(0) = 1, f(1) = 1. House Robber and Kadane (max-subarray) are the same shape with a max instead of a sum.
2 · 2D grid
Smell: a literal grid you move through, or any answer indexed by two coordinates where each cell flows from its neighbors above/left.
Canonical example: Min Path Sum — cheapest path from top-left to bottom-right moving only right or down.
State: f(i,j) = best to reach cell (i,j). Transition: f(i,j) = grid[i][j] + min( f(i-1,j), f(i,j-1) ). Base: first row/column accumulate in one direction. Fill rows top-to-bottom so dependencies are ready.
3 · Knapsack
Smell: a collection of items plus a numeric budget (weight, capacity, target sum), and you choose a subset to optimize value or hit the target.
Canonical example: Coin Change — fewest coins summing to an amount (unbounded: each coin reusable). Subset Sum / 0-1 knapsack is the each-item-once variant.
State: f(i, cap) = best using items up to i with budget cap. Transition: f(i, cap) = max( f(i-1, cap), value[i] + f(i-1, cap - cost[i]) ) — the two arms are skip item i vs include it and pay its cost. Base: zero items or zero budget → trivial value. (Unbounded uses f(i, cap - cost[i]) to reuse the same item.)
4 · Interval
Smell: a range [i,j] whose cost depends on where you split it — you pick a pivot k inside and combine the two halves.
Canonical example: Matrix Chain Multiplication (cheapest order to multiply a chain) or Burst Balloons.
State: f(i,j) = best for the subrange i..j. Transition: f(i,j) = min over k in (i,j) of ( f(i,k) + f(k,j) + combineCost ). Base: empty or single-element ranges cost 0. Fill by increasing range length so smaller intervals are ready before larger ones.
5 · Bitmask
Smell: a small set (n ≤ ~20) where the state is "which subset have I already used/visited," and order or pairing matters. A bitmask is an integer whose binary bits mark set membership — bit k set means "element k is in the subset."
Canonical example: Travelling Salesman — shortest route visiting all cities once.
State: f(mask, i) = best route ending at city i having visited exactly the cities in mask. Transition: extend by an unvisited j → f(mask | bit(j), j) = min(..., f(mask, i) + dist[i][j]). Base: f({start}, start) = 0. The 2ⁿ subsets are why n must stay small.
6 · String (two-sequence)
Smell: two strings (or sequences) you align character by character, deciding at each step whether the current pair matches.
Canonical example: Longest Common Subsequence; Edit Distance and Regex Matching are the same skeleton.
State: f(i,j) over the first i chars of A and first j of B. Transition: if A[i-1] == B[j-1] then f(i,j) = 1 + f(i-1,j-1); else f(i,j) = max( f(i-1,j), f(i,j-1) ). Base: empty prefix → 0 (matching against nothing). Palindrome problems are this with B = reverse(A) or an interval over one string.
Mapping a brand-new problem to an archetype
When a problem doesn't announce its shape, run this checklist and the state usually falls out:
- Name the decision. Write one sentence: "at each step I choose to ___." That verb (take/skip, go right/down, match/don't, split at k, visit next) names the archetype.
- List what changes after a decision. Whatever the next decision needs to know — your position, remaining budget, which set is used — is the state. Use the fewest facts that still make the recurrence correct.
- Write f in terms of smaller f. Each decision branch becomes one term; combine with min/max/sum/OR depending on whether you optimize or count.
- Pin the base cases and fill order. Identify the smallest states (empty, zero, single element) and choose an order where every cell's dependencies are already computed — or just memoize and let recursion handle order.
- Sanity-check the size. States × work-per-state is your time bound. If it's astronomically large (e.g. a bitmask with n = 40), the archetype fits but the constraints don't — rethink the state.
Pitfalls
- Wrong state — too little. Leaving out a fact the next decision needs makes the recurrence quietly incorrect (it returns plausible-but-wrong numbers). Classic: Kadane's
f(i)must mean "best subarray ending at i," not "best in 0..i" — the ending-at constraint is the missing fact, and the final answer is thenmaxover all i. - Wrong state — too much. Carrying facts that don't affect future decisions blows up the table and the runtime for nothing. Trim the state to what the transition actually reads.
- Missing or wrong base case. Forget
f(0)and you get an index error or a table seeded with garbage. The empty case (empty string, zero items, zero capacity) is the one people skip most. - Bad fill order in tabulation. Reading a cell before it's computed gives zeros/wrong values. Interval DP must iterate by range length; grid DP top-to-bottom, left-to-right. (Memoization sidesteps this — the recursion computes dependencies on demand.)
- Off-by-one between index and length. In string/grid DP,
f(i,j)usually means "first i / first j characters," so the character compared isA[i-1], notA[i]. Pick a convention and hold it. - 0-1 vs unbounded confusion. Recursing into
f(i-1, ...)uses each item once;f(i, ...)reuses it. Mixing them silently changes the problem.
Takeaway: DP works when a problem has overlapping subproblems (pieces repeat → caching helps) and optimal substructure (best-of-whole = combine best-of-parts → caching is correct). To solve one: name the repeated decision, let it pick the archetype, take the fewest facts you need as the state, write the transition as one term per decision branch, nail the base case, and either memoize (top-down) or tabulate (bottom-up) in dependency order. Six shapes — 1D linear, grid, knapsack, interval, bitmask, string — cover almost everything you'll be asked.
Go deeper (optional): the classic reference is CLRS (Introduction to Algorithms), chapter 15 on dynamic programming, which proves optimal substructure for several of these archetypes. Everything you need for interviews is in this lesson; the book is for the underlying theory.
House robber — skip-or-take with two rolling variables: