Dynamic Programming Patterns

The DP recipe, the classic templates, and how to recognize a DP problem in the wild.

The DP recipe

1. State: What does dp[...] mean? The fewest indices that pin a subproblem.
2. Transition: Express dp[state] from smaller states — the recurrence over choices.
3. Base cases: Smallest states set directly (empty prefix = 0, dp[0] = 1, …).
4. Order: Bottom-up table (iterate so deps come first) or top-down memo (recurse + cache).
5. Answer: Which state holds the result — often dp[n] or dp[n][m].

Kadane (max subarray): best_here = max(x, best_here + x) · track global max · O(n)
0/1 Knapsack: dp[i][w] = max(skip, take + dp[i-1][w-wi]) · O(n·W)
Coin change (min coins): dp[a] = min(dp[a], dp[a-coin] + 1) · O(n·A)
Longest increasing subseq.: dp[i] = 1 + max(dp[j] : a[j]<a[i]) = O(n²), or tails/patience O(n log n)
Longest common subseq.: match → dp[i-1][j-1]+1, else max(up, left) · O(n·m)
Edit distance: match → diagonal, else 1 + min(ins, del, replace) · O(n·m)

Rolling array: Only recent rows matter → drop a dimension, O(n·m) space becomes O(min(n,m))
Memo vs tabulation: Top-down recursion + cache is easy to write; bottom-up avoids stack + is often faster
Bitmask DP: State is a subset (TSP, assignment) → dp[mask], O(2ⁿ · n)
Deque / monotonic: Sliding-window max in transitions → amortized O(1) (also convex-hull trick)

Overlapping subproblems: The same smaller problem recurs many times — cache it
Optimal substructure: The best overall is built from best answers to subproblems
Count / min / max / feasible: Asking how many, best, or possible over a sequence of choices
Exponential brute force: Recursion with repeated states → memoize, then tabulate