Dynamic Programming

Why this matters / recognition signals

Dynamic programming is a way to make recursion fast by never solving the same subproblem twice. It applies when a problem has two properties, and both need to be true — not just one:

Optimal substructure: the optimal solution to the problem can be built from optimal solutions to its subproblems. Example: the shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C — you don’t need to reconsider the whole A-to-C problem once you trust the subpaths.
Overlapping subproblems: a naive recursive solution calls the same subproblem, with the same arguments, many times over. This is the part that specifically justifies caching. A problem can have optimal substructure without overlap (e.g., plain merge sort — the subarrays are disjoint, never repeated) and in that case DP buys you nothing over plain divide-and-conquer.

Recognition signals — reach for DP when the problem says:

“find the minimum/maximum/number of ways to…” over a sequence, grid, or set of choices
“can you reach/partition/make exactly X” using a subset of given items
The brute-force solution is “try every choice at every step” and choices at different steps don’t interact except through a small amount of shared state (an index, a remaining capacity, a remaining count)
Two strings/sequences being compared position by position (edit distance, LCS, subsequence matching)

Overlapping subproblems, concretely: naive Fibonacci

The textbook demonstration of “overlapping” is naive recursive Fibonacci. fib(n) = fib(n-1) + fib(n-2) has optimal substructure trivially, but the naive recursion tree recomputes the same calls exponentially many times:

flowchart TD
    F5["fib(5)"] --> F4a["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4a --> F3b["fib(3)"]
    F4a --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]
    F2a --> F1c["fib(1)"]
    F2a --> F0a["fib(0)"]
    F2b --> F1d["fib(1)"]
    F2b --> F0b["fib(0)"]
    F2c --> F1e["fib(1)"]
    F2c --> F0c["fib(0)"]

    style F3a fill:#5a3,color:#000
    style F3b fill:#5a3,color:#000
    style F2a fill:#e94,color:#000
    style F2b fill:#e94,color:#000
    style F2c fill:#e94,color:#000

fib(3) is computed 2 times, fib(2) 3 times, fib(1) 5 times — and this ratio gets exponentially worse as n grows. The call tree has O(2^n) nodes total, but only n+1 distinct subproblems (fib(0) through fib(n)) ever appear in it. That gap — exponentially many calls covering only linearly many distinct inputs — is exactly what “overlapping subproblems” means, and exactly what a cache exploits: store each distinct result once, look it up instead of recomputing, and the exponential tree collapses to O(n) work.

Two implementations of the same idea

Memoization and tabulation compute the identical recurrence; they differ only in direction.

Top-down (memoization): write the natural recursive solution, add a cache (map or array) keyed by the subproblem’s arguments, check the cache before recursing. Subproblems are solved in whatever order the recursion happens to visit them, driven by the original call.
Bottom-up (tabulation): identify the base cases, then iterate forward filling a table in an order that guarantees every cell’s dependencies are already computed by the time you reach it. No recursion, no call stack.

Tabulation is usually preferred in interviews once you’re comfortable with the recurrence — it avoids recursion-depth stack overflow on large inputs and is easier to reason about for space optimization (rolling arrays). Memoization is often easier to derive first, because it mirrors the brute-force recursive solution directly — write the brute force, add a cache, done.

The state-transition-recurrence checklist

This is the actual transferable skill — not memorizing individual problems, but a repeatable process for turning any new problem into a DP solution:

Define the state: what minimal set of parameters uniquely identifies a subproblem? (e.g., “the first i characters of s1 and the first j characters of s2” → state is (i, j).)
Define the recurrence/transition: given a state, how is its answer built from the answers to smaller states? This is almost always “try each choice available at this state, and take the best (or sum, or logical-OR) of the results.”
Define the base case(s): the smallest states, where the answer is known directly without recursing further (empty string, zero items, zero capacity).
Define where the final answer lives: often the “largest” state (dp[n], dp[amount], dp[m][n]), but not always — sometimes it’s the max/min over the whole table.

Skip any one of these four and the solution either doesn’t compile conceptually (missing base case → infinite recursion) or is silently wrong (missing states in the transition → undercounts).

Worked example: Coin Change (unbounded knapsack shape)

Problem: given coins [1, 3, 4], find the minimum number of coins to make amount 6. (0 if impossible.)

Apply the checklist:

State: dp[a] = minimum coins to make amount a.
Recurrence: dp[a] = 1 + min(dp[a - c]) over every coin c <= a that’s usable (unbounded — each coin can be reused, so we don’t reduce a “count of coins used” dimension).
Base case: dp[0] = 0 (zero coins needed to make amount zero).
Answer: dp[amount].

Bottom-up table fill, coins = [1, 3, 4], target = 6. Each cell only reads cells to its left (already computed), which is what makes the left-to-right fill order valid:

a	dp[a] before	check a-1=dp[?]	check a-3=dp[?]	check a-4=dp[?]	dp[a] after	how
0	—	—	—	—	0	base case
1	∞	dp[0]=0 → 1	—	—	1	1 coin: {1}
2	∞	dp[1]=1 → 2	—	—	2	2 coins: {1,1}
3	∞	dp[2]=2 → 3	dp[0]=0 → 1	—	1	1 coin: {3}
4	∞	dp[3]=1 → 2	dp[1]=1 → 2	dp[0]=0 → 1	1	1 coin: {4}
5	∞	dp[4]=1 → 2	dp[2]=2 → 3	dp[1]=1 → 2	2	2 coins: {1,4}
6	∞	dp[5]=2 → 3	dp[3]=1 → 2	dp[2]=2 → 3	2	2 coins: {3,3}

dp[6] = 2 (using two 3-coins). Every cell only ever looked at earlier, already-filled cells — that’s the same principle as the Fibonacci cache, just filled iteratively instead of via recursive lookups.

flowchart LR
    D0["dp[0]=0"] --> D1["dp[1]=1"]
    D0 --> D3["dp[3]=1"]
    D0 --> D4["dp[4]=1"]
    D1 --> D2["dp[2]=2"]
    D1 --> D4
    D1 --> D5["dp[5]=2"]
    D3 --> D4
    D3 --> D6["dp[6]=2"]
    D2 --> D5
    D4 --> D5
    D2 --> D6
    D3 --> D6
    style D6 fill:#5a3,color:#000

Java — top-down (memoized) and bottom-up (tabulated) Coin Change

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
 
public class CoinChange {
 
    // Top-down: memoization mirrors the brute-force recursion directly.
    public int coinChangeMemo(int[] coins, int amount) {
        Map<Integer, Integer> memo = new HashMap<>();
        int result = helper(coins, amount, memo);
        return result == Integer.MAX_VALUE ? -1 : result;
    }
 
    private int helper(int[] coins, int remaining, Map<Integer, Integer> memo) {
        if (remaining == 0) return 0;                 // base case
        if (remaining < 0) return Integer.MAX_VALUE;   // invalid path
        if (memo.containsKey(remaining)) return memo.get(remaining); // cache hit
 
        int best = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = helper(coins, remaining - coin, memo);
            if (sub != Integer.MAX_VALUE) {
                best = Math.min(best, sub + 1);
            }
        }
        memo.put(remaining, best);
        return best;
    }
 
    // Bottom-up: iterate amounts 1..target, each cell reads only earlier cells.
    public int coinChangeTabulation(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);   // sentinel for "unreachable"
        dp[0] = 0;                     // base case
 
        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a) {
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Python — top-down (memoized) and bottom-up (tabulated) Coin Change

from functools import lru_cache
 
 
def coin_change_memo(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def helper(remaining: int) -> int:
        if remaining == 0:
            return 0                     # base case
        if remaining < 0:
            return float("inf")          # invalid path
        return 1 + min(
            (helper(remaining - c) for c in coins),
            default=float("inf"),
        )
 
    result = helper(amount)
    return result if result != float("inf") else -1
 
 
def coin_change_tabulation(coins: list[int], amount: int) -> int:
    dp = [amount + 1] * (amount + 1)     # sentinel for "unreachable"
    dp[0] = 0                            # base case
 
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
 
    return dp[amount] if dp[amount] <= amount else -1

Second worked pattern: Longest Common Subsequence (2D table)

LCS is the canonical 2D DP — two strings, state needs both indices.

State: dp[i][j] = length of the LCS of s1[0..i) and s2[0..j).
Recurrence: if s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1] + 1 (extend the match); else dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (drop one character from either string, keep the better result).
Base case: dp[0][j] = dp[i][0] = 0 (an empty string has no common subsequence with anything).
Answer: dp[m][n] (bottom-right corner — both full strings consumed).

s1 = "ABCBDAB", s2 = "BDCABA" — a trimmed trace on prefixes "ABC" vs "BDC":

i \ j	B	D	C
""	0	0	0
A	0	0	0
B	1 (match B)	1	1
C	1	1	2 (match C, from dp[B][D]=1 +1)

Each cell only ever reads the cell above, to the left, or diagonally above-left — all guaranteed filled before the current cell if you fill row by row, left to right.

Complexity comparison

Approach	Time	Space	Notes
Naive recursion (no cache)	O(2^n) (Fibonacci-shape) or worse	O(n) call stack	Recomputes overlapping subproblems from scratch every time
Top-down memoization	O(states × work per state)	O(states) cache + O(depth) call stack	Only visits states actually reachable from the initial call
Bottom-up tabulation	O(states × work per state)	O(states), often reducible	Visits every state in the table, even unreachable ones
Tabulation + rolling array	Same time	O(previous row/column only)	Valid when `dp[i]` only depends on `dp[i-1]` (not the whole history) — e.g. coin change’s 1D array, or LCS reduced to two rows

Common pitfalls

Confusing “has recursion” with “needs DP”: recursion alone isn’t the signal — it’s recursion where the same subproblem is reached via multiple different paths. Divide-and-conquer (merge sort, binary search) recurses without overlap and gains nothing from memoization.
Wrong iteration order in tabulation: filling dp[a] using dp[a - coin] requires a - coin to already be computed — iterating amounts in the wrong direction (or filling the knapsack “0/1” table’s item dimension in the wrong order and using an item twice) is a common bug that only shows up on specific inputs.
0/1 vs unbounded confusion: 0/1 knapsack (each item usable once) needs the inner loop over capacity to go in reverse when using a 1D rolled array, so a cell isn’t updated using a value already updated in the same item’s pass; unbounded knapsack/coin change goes forward for exactly the opposite reason (reuse is intended).
Forgetting the base case entirely, or getting it subtly wrong: e.g. dp[0][j] = 0 for LCS looks trivial but omitting it (or initializing an array to 0 when the correct base should be -infinity for a “maximum” DP) silently produces wrong answers rather than a crash.
Off-by-one between “length” and “index”: 2D string DP is notorious for dp[i][j] referring to prefixes of length i/j, not indices i/j directly — mixing the two conventions mid-solution is the single most common LCS/edit-distance bug.

Practice problems

Climbing Stairs (simplest intro — 1D DP, dp[n] = dp[n-1] + dp[n-2], structurally identical to Fibonacci)
Coin Change (unbounded knapsack shape, worked above)
House Robber (1D DP with an adjacency constraint — “can’t pick two neighbors”)
Longest Common Subsequence (2D table, worked above)
Longest Increasing Subsequence (1D DP, O(n²) naive vs O(n log n) with patience sorting/binary search)
0/1 Knapsack (2D table, or 1D rolled with reverse iteration — contrast directly with Greedy Algorithms’s fractional knapsack)
Edit Distance (2D table, three transitions instead of two — insert/delete/replace)

Interview angles

“Is this problem DP, or can it be solved greedily?” — check whether a locally optimal choice can be proven to never need revisiting; if the choice at step i can be invalidated by information learned at step i+k, it’s DP, not greedy (see Greedy Algorithms for the formal contrast, e.g. 0/1 knapsack vs fractional knapsack).
“Can you reduce the space complexity?” — check whether dp[i] only depends on a fixed, small window of previous states (often just dp[i-1], sometimes dp[i-1] and dp[i-2]); if so, roll the array down from O(n) or O(m·n) to O(1) or O(n).
“Would you use memoization or tabulation here?” — memoization is faster to derive from a brute force and naturally skips unreachable states; tabulation avoids recursion depth limits and is easier to space-optimize. State a preference and justify it rather than treating them as interchangeable.
“Walk me through your recurrence before coding” — expect this to be asked explicitly; answer with the four-part checklist (state, recurrence, base case, answer location), not a jump straight to code.
“What if I also need to reconstruct the actual solution (not just the count/optimum)?” — keep a parallel table of choices made at each cell (or backtrack through the finished table by re-deriving which transition produced each cell’s value), then walk it backward from the answer cell.
“How would you detect overlapping subproblems in an unfamiliar problem?” — draw (or mentally trace) the naive recursion tree for a small input and check whether identical (argument) tuples recur; if the set of distinct argument tuples is small relative to the number of calls, that gap is the overlap.

Notes

Explorer