Dynamic Programming

DivideDivide and conquer works cleanly when a problem's subproblems don't overlap. Many important problems don't have that property — the same smaller subproblem recurs again and again across different branches of the recursion — and recomputing it every single time is wasted work. Dynamic programming, a term coined by Richard Bellman, is the general technique for avoiding that waste: solve each distinct subproblem once, store the answer, and reuse it every time it's needed again¹.

Overlapping Subproblems and Optimal Substructure

TwoTwo properties make a problem a dynamic-programming candidate: overlapping subproblems (the same smaller subproblem is needed more than once while solving the larger problem) and optimal substructure (an optimal solution to the whole problem is built from optimal solutions to its subproblems — the same requirement greedy algorithms need, but without greedy's additional greedy-choice guarantee). Where both hold, there are two equivalent ways to exploit them: memoization (write the recursive solution normally, but cache each subproblem's answer the first time it's computed, and check the cache before recomputing) and tabulation (build the answer up from the smallest subproblems first, filling a table iteratively, with no recursion at all). Memoization is usually easier to write, since it's just a cached version of the natural recursive definition; tabulation usually uses less memory and avoids any risk of recursion-depth limits, at the cost of having to work out the right iteration order by hand.

Worked Example: Edit Distance

TheThe edit distance between two strings is the minimum number of single-character insertions, deletions, and substitutions needed to turn one into the other — the same core idea behind a spell-checker's suggestions or a diff tool's output. Let d(i, j) be the edit distance between the first i characters of string A and the first j characters of string B. The recurrence: if the i-th and j-th characters match, d(i, j) = d(i-1, j-1) (no edit needed at this position); otherwise, d(i, j) = 1 + min(d(i-1, j), d(i, j-1), d(i-1, j-1)) — one plus the cheapest of deleting from A, inserting into B, or substituting, at this position.

       ""  C   A   T
  ""    0  1   2   3
  C     1  0   1   2
  U     2  1   1   2
  T     3  2   2   1

Filling this table for "CUT" against "CAT": the top-left 0 is the base case (empty against empty costs nothing); each cell is filled from the cell above, to the left, and diagonally above-left, using whichever of the recurrence's three cases applies — reading the bottom-right cell (1) gives the answer directly: "CUT" and "CAT" are one edit apart (substitute U for A), without ever having to explicitly enumerate and compare every possible sequence of edits.

Held-Karp and the Travelling Salesperson Problem

TheThe travelling salesperson problem — visit every city exactly once and return to the start, minimising total distance — has (n-1)!/2 possible routes to check by brute force, which is completely infeasible past a small handful of cities. The Held-Karp dynamic-programming formulation does much better by reframing the subproblem cleverly: rather than "the shortest route visiting these cities in this specific order" (which throws away reusable structure, since the same set of cities visited in different orders would each be tracked separately), it tracks "the shortest route that visits exactly this set of cities and ends at this specific city" — a state defined by a set and an endpoint, not a full ordered sequence. That reframing collapses the astronomically many possible orderings down to (city) × (subset of cities) states, giving O(n² · 2ⁿ) instead of the brute-force O(n!) — still exponential, and so still only practical for a few dozen cities at most, but a genuinely different and far smaller exponential than checking every full route by hand.

Floyd-Warshall: All-Pairs Shortest Paths

Dijkstra'sDijkstra's algorithm finds shortest paths from one source to everywhere else; the Floyd-Warshall algorithm finds shortest paths between every pair of nodes at once, and its dynamic-programming structure is worth seeing because it's unusually clean². The idea: consider, one at a time, whether allowing a path to route through each node k in turn ever gives a shorter path between any pair (i, j) than the best known so far — dist(i, j) = min(dist(i, j), dist(i, k) + dist(k, j)) — and after allowing routing through every node once, the table holds the true shortest distance between every pair.

Here dist(i, k) + dist(k, j) = 3 + 4 = 7, which is less than the direct edge's 10 — so once node k has been considered, dist(i, j) updates from 10 down to 7, exactly as the recurrence says. This is also directly the algorithm for computing a graph's transitive closure (which nodes can reach which other nodes at all, ignoring distance) — replace "minimum distance" with "is there any path," and the identical three-nested-loop structure answers a reachability question instead of a shortest-path one.

References