Dynamic Programming (DP) is a method for solving problems with overlapping subproblems by solving each subproblem once and storing the result. It turns exponential brute-force recursion into polynomial time at the cost of memory.
When to Reach for DP
A problem is a candidate for DP when it has two properties:
- Optimal substructure — the optimal solution is built from optimal solutions of subproblems.
- Overlapping subproblems — the same subproblem is computed repeatedly during recursion.
Classic signal: a naive recursive solution recomputes the same states. The Fibonacci recursion, for example, recomputes fib(n-2) twice, fib(n-3) three times, and so on.
The Two Flavors
- Memoization (top-down): keep the recursive structure, but cache results in a table before returning. Intuitive, but pays the recursion-call overhead.
- Tabulation (bottom-up): fill a table from the base cases upward using the recurrence. Faster, no recursion, but requires you to order states correctly.
Both compute the same table; choose memoization for clarity on complex states and tabulation for raw speed.
Designing the Recurrence
The hardest part of DP is defining the state — the minimal information that determines a subproblem’s answer. Ask three questions:
- What changes between subproblems? Those are your state dimensions (
i,w,j). - What decision does the recurrence make? Usually “include or skip”, “take this coin”, or “which character to align”.
- What are the base cases? The states you can answer without further recursion.
For 0/1 Knapsack: state = (items considered, capacity), decision = take/skip, base = zero items or zero capacity.
Common State Patterns
| Pattern | Example | State |
|---|---|---|
| Prefix of one array | LIS | i = ending index |
| Prefixes of two arrays | LCS | (i, j) = prefixes of both |
| Capacity dimension | Knapsack, Coin Change | (i, w) or (i, a) |
| Subarray intervals | Matrix chain | (l, r) = interval bounds |
Step-by-Step Recipe
- Write a brute-force recursive solution first.
- Identify the state from the changing parameters.
- Write the recurrence as
state → best(next states). - Add base cases.
- Implement top-down (memo) or bottom-up (table).
- If the problem asks for the solution itself (not just its value), add a reconstruction pass that walks the table backward.
Practice Trajectory
Start with 1D states (Fibonacci, LIS, house robber), move to 2D states (LCS, knapsack, coin change), then intervals (matrix chain), then bitmask DP for small sets. DP is a skill built by volume — each problem teaches a new state shape.