When memoization applies

Memoization is a one-line idea — cache the answers to function calls and reuse them — that turns some exponential algorithms into polynomial ones and does absolutely nothing for others. The skill is knowing which is which before you’ve written anything, and it comes down to two properties with unglamorous names: overlapping subproblems and optimal substructure. This page makes both concrete, because “when does DP apply?” is the interview question hiding behind every DP problem.

Property one: the same question must recur

Naive recursive Fibonacci is the canonical demonstration: fib(50) calls fib(49) and fib(48); fib(49) calls fib(48) again — and the tree beneath repeats itself so aggressively that fib(20) is computed thousands of times and the whole thing costs O(2ⁿ). There are only 50 distinct questions in sight; the recursion just asks them exponentially many times. Cache the 50 answers and the cost collapses to O(n). That’s overlapping subproblems: the recursion revisits identical states.

The contrast that makes the property visible: merge sort also recurses, but its two halves are different subarrays — no call is ever repeated, there’s nothing to cache, and memoizing it buys literally nothing. Divide-and-conquer without overlap is not DP. The quick diagnostic: count the distinct states versus the recursion tree’s size. LCS on two strings of length n has an exponential tree but only n² distinct (i, j) prefix-pairs — massive overlap, hence the table. If distinct states ≈ tree size, caching is dead weight.

Property two: small answers must build big ones

Caching is only legal if a subproblem’s answer is a fact — independent of how you arrived at it. Optimal substructure says the optimal answer to the big problem is composed from optimal answers to subproblems: the shortest path from A to C through B contains, as a piece, the shortest path from A to B. Edit distance’s cell (i, j) can be the min over three neighbours precisely because each neighbour is the true answer for its prefixes, not an artifact of one exploration order.

The property fails more often than beginners expect, and the failures are instructive. Longest simple path in a graph: the best path from A to B might reuse vertices that the continuation to C needs — the “subproblem answer” depends on which vertices the rest of the path consumes, so a cached number keyed by node alone is meaningless (and the problem is, in fact, NP-hard). The repair, when one exists, is always the same move: enlarge the state until the answer becomes history-independent. Path problems key by (node, set-of-visited) — legal again, but the state space went exponential, which is bitmask DP’s territory and only viable for n ≈ 20. When someone asks “why can’t DP solve longest path?”, this is the answer: not “it can’t”, but “the honest state is exponentially large”.

Top-down or bottom-up — a smaller choice than advertised

Memoization (top-down) is the recursion you already had plus a cache: write the recurrence naturally, add @cache, done — and it computes only reachable states, which matters when the state space is sparse. Tabulation (bottom-up) fills the table in dependency order with a loop: no recursion depth risk, usually faster constants, and it exposes the space optimization — when each row depends only on the previous, two rows suffice, as the edit distance essay shows. They compute the same values; pick top-down to find the solution quickly and bottom-up to ship it, and say exactly that sentence when asked to compare them.

The recognition kit

Phrases that advertise DP: count the ways, minimum cost to reach, longest/shortest subsequence, can it be partitioned/formed, maximum profit with choices at each step. Structure that advertises it: a decision at each step whose consequences are summarized by a small “where am I now” state — index into an array, pair of prefix lengths, remaining capacity, last choice made. The design protocol, in order: (1) define the state in words — “dp[i][w] = best value using the first i items within weight w” — before any recurrence; (2) write the recurrence as the choice at that state; (3) locate base cases; (4) check the two properties; (5) count states × work-per-state, which is the complexity with no further analysis needed. Most DP failures in interviews are step 1 skipped: a recurrence over an undefined state is guesswork with subscripts.

Where it genuinely doesn’t apply

Greedy-solvable problems (interval scheduling, Dijkstra’s settling) have optimal substructure and a stronger property — a locally best choice that’s globally safe — so DP works but overpays. No-overlap recursion (merge sort, quicksort, tree computations on distinct subtrees) caches nothing. History-dependent problems without a tolerable state enlargement (longest simple path, most puzzles about sequences with global constraints) refuse DP outright. And backtracking problems like N-Queens sit in a useful middle: subproblems don’t overlap (each partial board is unique), so no memo — but the pruning discipline is the same “kill whole subtrees early” economy by other means. Knowing which regime a problem lives in is worth more than any particular table you’ve memorized.