Chapter 10. Dynamic Programming

Solve overlapping subproblems once, memoize each answer, and combine them into the solution for the whole problem.

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

Those four LLP forms are below, each with a runnable demo. The classical implementations live on the classical forms page.

Setting

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

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

Recursion alone is exponential; memoization 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). $$ 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]$. 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 minimizing 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). $$ 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 maximizing 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]$. 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.

The LLP perspective

Each algorithm below views its DP table as a vector $G$ in a finite distributive lattice, with a lattice-linear predicate $B$ whose least satisfying vector is exactly the table the classical recurrence computes. The bottom-up fill above is one schedule of forbidden/advance steps; the LLP form admits others, including concurrent ones.

LLP-WeightedIntervalScheduling

$G[j]$ is $Opt(j)$. Forbidden: $j \geq 1$ and $G[j]$ hasn't reached $\max(G[j-1],\ w_j + G[p(j)])$ yet. Advance sets $G[j]$ to that value. Because the dependency graph $j \to j-1$ and $j \to p(j)$ is a DAG, any schedule that eventually revisits every forbidden index converges to the same $Opt$ values as the bottom-up fill.

LLP-LIS

$G[j]$ is the length of the longest increasing subsequence ending at $j$. With $\mathrm{pre}(j) = \{i < j : A[i] < A[j]\}$, index $j$ is forbidden when some predecessor $i \in \mathrm{pre}(j)$ has $G[i] + 1 > G[j]$; the advance sets $G[j]$ to $\max_{i \in \mathrm{pre}(j)} G[i] + 1$ (or keeps $1$ when $\mathrm{pre}(j)$ is empty).

LLP-OptimalBinarySearchTree

$G[i, j]$ is the least cost of a BST on keys $i..j$. Forbidden: some split point $k$ would lower the cost below $G[i,k-1] + s(i,j) + G[k+1,j]$. The book's priority annotation schedules ranges by increasing width $(j - i)$ so each entry is computed once; without a real priority queue, this demo instead repeatedly rescans every range until none is forbidden — same final table, more steps.

LLP-Knapsack

$G[i, c]$ is the best value using items $1..i$ within capacity $c$. Two forbidden/advance rules over the same $(i,c)$ index raise it: forbidden when $G[i,c] < G[i-1,c]$, advance to $G[i-1,c]$; and forbidden when $w_i \leq c$ and $G[i,c] < G[i-1,c-w_i] + v_i$, advance to that value. Converges to $G[i,c] = \max(G[i-1,c],\ G[i-1,c-w_i] + v_i)$.