Foundations
Dynamic Programming
Solve each subproblem once, reuse the answer. The hardest part is seeing the recurrence.
What is dynamic programming?
Dynamic programming applies to problems with two properties: overlapping subproblems (a naive recursion solves the same subproblem multiple times) and optimal substructure (the optimal solution to the whole problem can be assembled from optimal solutions to its subproblems). When both hold, the naive exponential recursion collapses to polynomial time by caching each subproblem result the first time it is computed.
The key insight is that caching is enough. For Fibonacci, computing fib(40) naively recomputes fib(2) billions of times. Memoize and each of the 40 unique subproblems is computed exactly once - O(n) instead of O(2^n). The cache is the only structural change.
Two approaches implement this caching. Top-down (memoization) starts from the full problem, recurses into subproblems, and stores each result in a dict keyed by the subproblem's state. Bottom-up (tabulation) fills a DP array iteratively from the smallest subproblems upward. Both produce the same answer with the same asymptotic complexity. Bottom-up avoids recursion overhead, enables space optimization by discarding old rows, and eliminates call stack limits - but the recursive structure of top-down is often easier to derive when you first encounter a problem.
Identify DP problems by the shape of their question: "count all ways", "find the minimum cost", "find the maximum value", or "is this achievable" - combined with choices at each step that produce overlapping subproblems. Greedy also optimizes, but greedy makes the locally best choice at each step without reconsidering. DP considers all choices and keeps the globally best - it pays for that guarantee with a table of subproblem results.
Core operations
| Variant | Direction | Cache structure | Best when |
|---|---|---|---|
| Top-down (memoization) | Full problem to subproblems | memo dict keyed by state | Natural recursive structure; sparse state space |
| Bottom-up (tabulation) | Subproblems to full problem | 1D or 2D array | Dense state space; want to avoid recursion |
| Space-optimized bottom-up | Same as tabulation | Rolling variables or single row | dp[i] depends only on dp[i-1] or previous row |
Key patterns
1D tabulation (linear DP)
Fill a one-dimensional array from the smallest subproblem up, where each entry is the answer for one input size.
When to use - the answer for size index depends on a few smaller sizes, and a naive recursion would recompute those smaller answers over and over. The state is a single number: "using the first index elements" or "for value index". Fibonacci, climbing stairs, house robber, and coin change all fit. Caching collapses the exponential recursion to a single linear pass.
How it works - define the state as dp[index] and write the transition that relates it to one or more smaller indices, then set the base case dp[0] so the first real entries compute correctly. Fill the array left to right: by the time you reach index, every smaller entry it reads is already final. This is the bottom-up form - the same caching a memoized top-down recursion would do, just without the call stack. Building the whole table is O(n) time and O(n) space, and O(1) space when each entry only looks back a fixed distance.
Example: count ways to climb stairs. Given n = 6, the table seeds dp[1] = 1 (one way) and dp[2] = 2 (two ways). Every later entry adds its two predecessors: dp[3] = dp[2] + dp[1] = 2 + 1 = 3, then dp[4] = 3 + 2 = 5, dp[5] = 5 + 3 = 8, and dp[6] = 8 + 5 = 13, so there are 13 ways to climb six stairs taking one or two steps at a time. The visualizer below fills the table one step at a time.
dp[0] is the empty-input base case, not the answer for input 0 - in many 1D DP problems dp[0] is set to 0 or 1 to represent "zero cost for zero items." Forgetting this base case makes dp[1] and dp[2] wrong and cascades through every subsequent entry.2D tabulation (grid and string DP)
Fill a grid where each cell is the answer for a prefix of one sequence against a prefix of another.
When to use - the problem aligns or compares two sequences, so the natural state is a pair of indices, one into each. Edit distance, longest common subsequence, and unique paths all have this shape. Trying every alignment by recursion is exponential; the grid has only m x n distinct cells, so filling it once is polynomial.
How it works - define the state as dp[i][j] for the first i elements of sequence A and the first j of sequence B, with an extra row and column of zeros as the empty-prefix base cases. Write the transition for one cell - it reads the cell above (dp[i-1][j]), to the left (dp[i][j-1]), or diagonally above-left (dp[i-1][j-1]) - then fill row by row so every neighbor a cell needs is already done. The answer lands in the bottom-right cell. Filling the table is O(m x n) time and O(m x n) space, reducible to one row when each cell only reads the row above it.
Example: longest common subsequence. Given corvette against cove, the matches each extend the diagonal: c sets dp[1][1] = 1, o sets dp[2][2] = 2, v sets dp[4][3] = 3, and the e at row 5 lifts dp[5][4] to 4. The later e at row 8 keeps the max at 4, so the bottom-right cell dp[8][4] returns 4, the length of cove. The visualizer below fills the grid cell by cell.
i - 1 and j - 1, not i and j - the extra row and column of zeros are the empty-string base cases, so dp[i][j] corresponds to text1[i-1] and text2[j-1]. Using i and j directly is the most common off-by-one bug in 2D DP.Decision DP (include/exclude)
At each element you take it or leave it, and keep the better of the two resulting subproblems.
When to use - every element presents the same binary choice - include it or skip it - and taking one constrains what you can take next (rob this house and you must skip the neighbor, pack this item and the capacity shrinks). House robber and 0/1 knapsack are the canonical examples. Enumerating every subset is O(2^n); folding the choice into a recurrence keeps only the best running answer per state.
How it works - the state is the index you are deciding on (and, for knapsack, the remaining capacity). The transition is dp[index] = max(exclude, include): exclude carries the best answer without this element, include adds this element's value to the best answer from the subproblem it leaves behind. The base case is the empty input, where the best answer is zero. Fill the states in order so both branches read already-final entries; the optimal-substructure guarantee is what makes keeping only the max at each step correct.
Example: house robber. Given [2, 7, 9, 3, 1], the table seeds dp[0] = 2 and dp[1] = max(2, 7) = 7. House 2 takes the include branch with dp[2] = dp[0] + 9 = 11; house 3 finds include worth only dp[1] + 3 = 10 and keeps 11 by excluding; house 4 includes again for dp[2] + 1 = 12. The winning plan robs the 2, the 9, and the 1 for 12 - the visualizer below plays out each include/exclude decision.
When to reach for dynamic programming
- The problem asks for the minimum cost, maximum value, or total count of ways to reach a goal, and choices made early affect later options.
- A recursive solution is correct but exponentially slow because the same subproblems repeat - add memoization and the solution is complete.
- At each step you face a binary choice (include or exclude, rob or skip) and the locally greedy choice does not always win globally.
- The problem asks "can you make X from a set of values?" - coin change, subset sum, and knapsack all have this shape.
- Two sequences are being compared or aligned - edit distance, LCS, or regex matching - and an index into each sequence is the natural state.
- The answer for a large input can be defined recursively in terms of answers to smaller inputs of the same type and those smaller inputs overlap.
- The problem appears to require trying all combinations but the search space grows polynomially in distinct subproblems, not exponentially.
Done reading? Mark it so it sticks in your dashboard.