Coding Prep
Dynamic Programming
Breaking problems into overlapping subproblems and caching results - top-down memoization for natural recursion and bottom-up tabulation for space-efficient iteration.
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.
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.
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.
Canonical examples
Coin change (minimum coins for a target amount)
The insight: define dp[amount] as the minimum number of coins needed to make amount. For each amount from 1 to the target, try every coin denomination - if the coin is small enough, it could be the last coin used, so dp[amount - coin] + 1 is a candidate answer. Take the minimum over all valid coins. Initialize dp[0] = 0 (zero coins for zero amount) and every other entry to infinity - if an entry is still infinity after filling, that amount is unreachable.
Longest common subsequence
The insight: dp[i][j] is the length of the LCS of the first i characters of text1 and the first j characters of text2. If the characters at position i and j match, they extend the best alignment of everything before them: dp[i][j] = dp[i-1][j-1] + 1. If they do not match, the best alignment skips one character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The answer accumulates in dp[m][n].
dp[n] holds the minimum coin count or LCS length, but not which coins were used or which characters were matched. Recovering the actual solution requires tracing backward through the filled table, following the cells that contributed to each answer.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.
Practice problems
- Climbing Stairs - 1D DP with a Fibonacci recurrence; the simplest introduction to the pattern.
- House Robber - Decision DP with an include/exclude choice and a gap constraint.
- Coin Change - 1D unbounded knapsack; initialization to infinity is the key detail.
- Longest Increasing Subsequence - 1D DP where each cell looks back at all previous cells; O(n log n) variant uses patience sort.
- Unique Paths - 2D grid DP with a clean two-direction recurrence.
- Longest Common Subsequence - 2D string DP; the template for all sequence alignment problems.
- Word Break - 1D DP with a set lookup; tests whether you can construct the full DP state from partial results.
Done reading? Mark it so it sticks in your dashboard.