DP is the answer when the problem has overlapping subproblems and optimal substructure — recursive solutions that recompute the same subcomputations. The discipline: identify the state, write the recurrence, decide top-down (memo) vs bottom-up (table).
The two questions that decide the state
- What does a partial solution depend on? That’s the state.
- What’s the smallest piece of “input consumed so far” that still determines future choices? Often an index, a remaining capacity, a last-action flag.
If the state has more than 2–3 dimensions, suspect you’re including non-essential information, or the problem isn’t actually DP.
Top-down vs bottom-up
- Top-down (memoized recursion). Easier to write — the recurrence is the code. Only computes states you actually need. Costs: stack depth, dict overhead.
- Bottom-up (table fill). Often faster (cache-friendly, no function-call overhead), enables space optimization (rolling arrays). Costs: you must compute states in dependency order; harder to write for non-obvious orderings.
Default: write top-down to validate correctness, convert to bottom-up if memory or speed matters.
Recurrence patterns to recognize
| Family | Shape | Example |
|---|---|---|
| Linear | dp[i] = f(dp[i-1], dp[i-2], ...) | Fibonacci, climbing stairs, house robber |
| Two-pointer | dp[i][j] = f(dp[i±1][j±1]) | Edit distance, LCS, palindrome substring |
| Knapsack | dp[i][w] over items × capacity | 0/1 knapsack, subset sum, coin change |
| Interval | dp[i][j] over ranges | Matrix chain, balloon burst |
| State machine | dp[i][state] | Stock with cooldown, paint house |
| Tree DP | dp[node] computed from children | House robber III, max path sum |
| Bitmask | dp[mask] or dp[i][mask] | TSP small N, assignment |
Space optimization
Most linear DPs only depend on the previous row → reduce dp[i][j] to dp[j] rolling. Watch the iteration order: 0/1 knapsack iterates w backwards to prevent reusing the same item.
When DP is the wrong tool
- Greedy choice works. If a local optimum is provably global (interval scheduling, Huffman), greedy beats DP.
- State space is too large. If your state has more than ~10⁷ entries, DP doesn’t fit in memory; you need approximation, randomization, or a different formulation.
- No overlap. If recursive subproblems are all distinct, memoization buys nothing — it’s just recursion.
In production
You almost never write DP at work. Where it does show up: regex compilation, parser generators, diff algorithms, query optimizers (join ordering is interval DP), spell-check (edit distance), compression. Knowing the shape helps you read these systems’ source.