Dynamic programming solves problems that have optimal substructure (an optimal solution can be built from optimal solutions to subproblems) and overlapping subproblems (the same subproblems are encountered repeatedly). Caching subproblem solutions turns exponential brute force into polynomial.
The thinking pattern
1. Define the state — what determines a subproblem? (e.g., "longest increasing subsequence ending at index ") 2. Write the recurrence — express the state in terms of smaller states. 3. Identify base cases. 4. Decide on direction — top-down with memoization or bottom-up with tabulation.
Memoization vs tabulation
Both store subproblem solutions. They differ in how they fill the table.
- Memoization (top-down): write the natural recursion, then cache results. Computes only the subproblems you actually reach. Easy to write; uses recursion stack space.
- Tabulation (bottom-up): iterate through states in dependency order, filling a table. No recursion. Often faster in practice (no function-call overhead, better cache behavior) but requires you to figure out the iteration order yourself.
Pick memoization when the recurrence is natural and only a sparse subset of states is reached. Pick tabulation when iteration order is obvious and you want to optimize space (often you can keep just the last row instead of the whole table).
Why exponential becomes polynomial
The recurrence tree of a brute-force solution may have leaves, but distinct subproblems number only . With caching, each subproblem is computed once. Cost = (number of distinct subproblems) × (work per subproblem).
Three classic recurrence shapes
- Linear: depends on (and maybe ). Examples: Fibonacci, climbing stairs, longest increasing subsequence (after formulation).
- 2D: depends on , , . Examples: edit distance, longest common subsequence, grid pathfinding.
- Interval: depends on and for . Examples: matrix chain multiplication, optimal BST, palindrome partitioning.