Dynamic Programming Patterns
Dynamic programming is the topic people most often try to learn by memorising problems, which is the slowest possible route. Every dynamic program is three decisions: what the state is, how a state is built from smaller states, and what the base cases are. Once those are written down the code is mechanical. The patterns below are worth learning as a sequence, because each introduces exactly one new kind of state.
Where to start, and what comes next
- 01
1D DP
One index, one dimension. Climbing stairs and coin change establish the state-and-transition habit with nothing else in the way.
- 02
2D DP
Two indices, which covers knapsack, grid paths and any comparison of two sequences. The largest and most reused family.
- 03
Stock / State Machine
State machines, where the state is a situation rather than a position. A different mental model and a common interview family.
- 04
LIS Pattern
Longest increasing subsequence, both the O(n squared) version and the patience-sorting one, which is where binary search enters DP.
- 05
Interval DP
Ranges rather than prefixes, where the recurrence asks which element is handled last. A genuine step up in difficulty.
- 06
Tree DP
DP over a tree instead of an array, where children return values to a parent. Straightforward once tree recursion is comfortable.
- 07
Bitmask DP
A set as the state, encoded in the bits of an integer. Last because it is the least common and assumes the bit manipulation topic.
If you only have time for three things
- Writing the state and the transition in words before any code. Most wrong answers here are wrong states, not wrong loops.
- 0/1 knapsack, including why the one-dimensional version iterates capacity downward and the unbounded version upward.
- The two-sequence table shape, which serves edit distance, longest common subsequence and their variants unchanged.
Start with the recursion, then add memoization, then convert to a table if it helps. That order is easier to reason about out loud and it shows the derivation rather than a memorised result. If you go straight to a filled table, expect to be asked where the recurrence came from, and be able to answer.
The idea underneath
The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.
Problems that use these patterns
Head to head
Questions people ask
How do I find the state?
Ask what you would need to know to solve the rest of the problem if you were dropped into the middle of it. That set of facts is the state. If your answer includes something you cannot index cheaply, the state is probably too large.
Memoization or tabulation?
Memoize first, since it is the recursion plus a cache and is harder to get wrong. Convert to tabulation when the recursion is too deep for the stack, or when you want to collapse the table to one row and save memory.
Why must 0/1 knapsack iterate capacity downward?
Because the one-dimensional array is reused across items. Going upward would let dp[w - weight] already include the current item, so it would be taken twice. Iterating downward guarantees you read the previous item's row. Unbounded knapsack wants that reuse and so iterates upward.