Chapter 10. Dynamic Programming

Solve overlapping subproblems once, memoise, and combine. The LLP recasting turns each table fill into a fixed-point search.

This page: chapter setup and problem statements. View classical algorithms »

The lattice-linear (LLP) reformulations of these algorithms described in the book are part of the parallel edition only and are not included in this companion site's sequential-edition scope. The classical, sequential implementations live on the classical forms page.

Setting

A dynamic programming algorithm captures an optimisation problem whose optimal solution can be assembled from optimal solutions to overlapping subproblems. Three ingredients suffice:

1. identify the sub-problem structure — typically indexed by intervals $[i, j]$, prefixes $1..j$, or item-and-capacity pairs $(i, c)$;
2. write a recurrence that expresses the optimum for each sub-problem in terms of strictly smaller sub-problems;
3. fill the resulting table in any topological order respecting the recurrence.

Recursion alone is exponential; memoisation makes it polynomial. Bottom-up table-fill matches that complexity without the recursion stack. The LLP recasting goes one step further: the table is the least vector $G$ in a finite distributive lattice satisfying a lattice-linear predicate, and the table-fill order is just one valid LLP schedule among many.

Weighted Interval Scheduling

Given $n$ intervals with start time $s_i$, finish time $f_i$, and weight $w_i$, sorted by finish time, choose a subset of pairwise-compatible intervals (no two overlap) of maximum total weight. The plain greedy from Chapter 6 fails when weights vary, but DP succeeds. Let $p(j)$ be the largest index $i < j$ with $f_i \leq s_j$ (and $p(j) = 0$ when no such $i$ exists). Define $Opt(j)$ = the maximum weight using intervals $1, \ldots, j$. Then $$ Opt(0) = 0, \qquad Opt(j) = \max\bigl(Opt(j-1),\ w_j + Opt(p(j))\bigr). $$ Sequential running time: $O(n)$ once $p$ is in hand, $O(n \log n)$ with binary search to build $p$.

Longest Increasing Subsequence

Given an array $A[1..n]$, find a strictly increasing subsequence of maximum length. Let $dp[j]$ be the length of the longest increasing subsequence ending at index $j$. Then $dp[j] = 1 + \max\{dp[i] : i < j,\ A[i] < A[j]\}$ (or $1$ when no such $i$ exists). The LIS length is $\max_j dp[j]$. Sequential running time: $O(n^2)$. There is also an $O(n \log n)$ patience-sort variant using binary search.

Optimal Binary Search Tree

Given $n$ keys with access frequencies $p[0..n-1]$, build a binary search tree minimising the expected depth-weighted access cost $\sum_i p[i] \cdot \mathrm{depth}(i)$. Let $dp[i][j]$ be the minimum cost of a BST built from keys $i..j$, and $s(i, j) = \sum_{k=i}^{j} p[k]$. If key $r$ is the root of the optimal subtree on $i..j$, the contribution decomposes as $$ dp[i][j] \;=\; \min_{i \leq r \leq j} \bigl(dp[i][r-1] + dp[r+1][j]\bigr) + s(i, j). $$ Sequential running time: $O(n^3)$. Knuth's monotonicity refinement reduces this to $O(n^2)$.

0/1 Knapsack

Given items with weights $w_i$ and values $v_i$ and a knapsack capacity $W$, choose a subset of indivisible items maximising total value subject to the weight constraint. Let $G[i][c]$ be the maximum value using items $1, \ldots, i$ within capacity $c$. Then $$ G[i][c] \;=\; \begin{cases} G[i-1][c] & w_i > c, \\ \max\bigl(G[i-1][c],\ G[i-1][c - w_i] + v_i\bigr) & w_i \leq c. \end{cases} $$ The optimum is $G[n][W]$. Sequential running time: $O(nW)$ — pseudo-polynomial because the cost depends on the magnitude of $W$, not just the number of bits in its representation.

The fractional version (where $x_i \in [0, 1]$) is solved by a simple greedy on value-density and lives in Chapter 6.