Dynamic Programming

Dynamic programming is recursion plus memory: when a recursive solution solves the same subproblems repeatedly, caching them collapses exponential work to polynomial. The technique is mechanical once the state is right — and state design is the actual skill. This page teaches DP the way it is used: a recipe, the classic problem families as templates, and the optimizations that matter.

The recipe

Define the state: what parameters uniquely identify a subproblem? (This is 80% of the difficulty.)
Write the recurrence: express the answer for a state in terms of smaller states — including the choice being made.
Identify base cases.
Order the computation: top-down memoization (write the recursion, add a cache) or bottom-up tabulation (fill a table in dependency order).
Recover the solution if needed: store the choice made at each state, walk back from the end.

Memoization vs tabulation is mostly taste: memoization is nearer the math and skips unreachable states; tabulation avoids recursion depth limits and enables space optimization. Complexity is always (number of states) × (work per state) — a formula worth computing before writing code.

Fibonacci, the toy that teaches the point

Naive $\mathrm{fib}(n) = \mathrm{fib}(n-1) + \mathrm{fib}(n-2)$ recomputes subproblems exponentially ( $O(\phi^n)$ calls). One dictionary turns it into $O(n)$ ; observing you only ever need the last two values turns the table into two variables — the space-optimization move in miniature.

The classic families as templates

0/1 Knapsack — state: (items considered, capacity used); recurrence: take or skip item $i$ :

V[i][w] = \max\big(V[i-1][w],\; V[i-1][w - w_i] + v_i\big)

$O(nW)$ — pseudo-polynomial: polynomial in the numeric value $W$ , exponential in its bit-length, which is why knapsack can be NP-hard and DP-solvable at once. Template for: subset-sum, partition, coin change, budget allocation.

Edit distance (Levenshtein) — state: (prefix of $a$ , prefix of $b$ ); recurrence: match/replace, insert, or delete:

D[i][j] = \min\big(D[i-1][j-1] + [a_i \ne b_j],\; D[i-1][j] + 1,\; D[i][j-1] + 1\big)

$O(nm)$ . Template for: sequence alignment (bioinformatics scoring matrices are this recurrence with different constants), diff tools, fuzzy matching — the mechanism inside MP3Resolver's duplicate detection.

Longest common subsequence — the same grid with match/skip choices; diff and merge tools live here.

Interval/chain DP — state: (left, right) over a span; matrix-chain multiplication, optimal BSTs, polygon triangulation. $O(n^3)$ typically.

DP on DAGs — longest/shortest paths, counting paths: any DP is a shortest-path problem on its implicit dependency DAG, computed in topological order. This lens unifies the whole subject — and connects it to Dijkstra and Bellman-Ford, which are DP with priority-queue and edge-relaxation orderings respectively.

DP over subsets (bitmask DP) — state: a subset encoded as bits; Held-Karp solves TSP in $O(n^2 2^n)$ — exponential, but a vast improvement on $n!$ , and the honest ceiling for exact small-instance solutions.

Space optimization

When the recurrence references only the previous row/layer, keep only that: knapsack drops from $O(nW)$ to $O(W)$ space (iterate capacity downward to avoid self-interference — the classic subtle bug), edit distance from $O(nm)$ to $O(\min(n,m))$ . Hirschberg's trick recovers the actual alignment in linear space by divide-and-conquer on the DP — the two paradigms composing.

When DP does not apply

No optimal substructure (longest simple path — subpaths interfere via the simplicity constraint) or no overlap (then plain divide and conquer suffices). And when the state space itself is exponential and unstructured, DP degrades into enumeration — the signal to switch to branch-and-bound or heuristics.

Going further

This page is the fundamentals course. For the advanced optimization patterns — Convex Hull Trick, divide-and-conquer optimization, Knuth's optimization, DP on trees, digit DP — see Dynamic Programming Patterns, the competition-grade sequel.