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: LLP forms. View classical forms »

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.

The LLP perspective

Each DP table is the least vector $G$ in a finite distributive lattice satisfying a monotone family of inequalities — exactly a lattice-linear predicate $B$. The bottom-up fill is one schedule; any topological order over the dependency DAG works, and many indices can advance in parallel.

• LLP-WIS. $G[j] \geq \max(G[j-1],\ w[j] + G[p[j]])$. The least $G$ satisfying both is exactly $Opt$. A "fixed" flag schedules each index once, after both predecessors are settled.
• LLP-LIS. $G[j] \geq G[i] + 1$ for every $i \in pre(j)$, where $pre(j) = \{i < j : A[i] < A[j]\}$. The least feasible $G$ has $G[j]$ equal to the longest-increasing-subsequence length ending at $j$.
• LLP-OBST. $G[i, j] \geq \min_r\bigl(G[i, r-1] + G[r+1, j]\bigr) + s(i, j)$. The book uses a priority schedule on $j - i$ so each cell advances once.
• LLP-Knapsack-Step. Adding one item: $G[c] \geq C[c]$ and $G[c] \geq C[c - w] + v$ when $c \geq w$, where $C$ is the previous row. Each $c$ advances in $O(1)$; the full knapsack is $n$ such steps.

The LL DSL versions ship in book/lang/progs-dp/. Each demo below mirrors one of those programs.

LLP-WeightedIntervalScheduling

LLP form on the $G$ vector. Index $j$ is forbidden whenever $G[j] < \max(G[j-1],\ w[j] + G[p[j]])$; the advance lifts $G[j]$ to that maximum. The least vector satisfying both inequalities is exactly $Opt(j)$.

Time complexity: $O(n)$ once $p$ is in hand, $O(n \log n)$ to compute $p$, where $n$ is the number of intervals.

int[] LLPWeightedIntervalScheduling(int[] w, int[] p) {
  int[] G = 0;
  forbidden (j) :
    j >= 1 && G[j] < maxRhs(j)
  =>
    advance :
      G[j] = maxRhs(j);
  return G;
}

int maxRhs(int j) {
  int skip = G[j - 1];
  int take = w[j] + G[p[j]];
  if (take > skip) { return take; } else { return skip; }
}

LLP-LIS

LLP form on the per-index LIS-length vector. Index $j$ is forbidden whenever some predecessor $i \in pre(j) = \{i < j : A[i] < A[j]\}$ already has $G[i] + 1 > G[j]$; the advance sets $G[j]$ to the maximum of $\{G[i] + 1 : i \in pre(j)\}$.

Time complexity: $O(n^2)$, where $n$ is the size of the array.

int[] LLPLongestIncreasingSubseq(int[] A, set<int>[] pre) {
  int[] G = 1;
  forbidden (j) :
    exists i in pre[j] : G[j] < G[i] + 1
  =>
    advance :
      G[j] = max i in pre[j] : G[i] + 1;
  return G;
}

LLP-Knapsack-Step

A single-item LLP step: given the previous row $C$ of the knapsack table and a new item of weight $w$ and value $v$, compute the next row $G$. Index $c$ is forbidden whenever $G[c] < C[c]$ or (when $c \geq w$) $G[c] < C[c - w] + v$. The full $0/1$ knapsack is $n$ such steps; together they re-derive the standard $O(nW)$ table fill.

Time complexity: $O(W)$ per item, $O(nW)$ for the full knapsack, where $W$ is the capacity and $n$ is the number of items.

int[] LLPIncrKnapsack(int w, int v, int[] C) {
  int[] G = 0;
  forbidden (j) :
    G[j] < C[j] || (j >= w && G[j] < C[j - w] + v)
  =>
    advance :
      G[j] = newValue(j);
  return G;
}

int newValue(int j) {
  int skip = C[j];
  if (j >= w) {
    int take = C[j - w] + v;
    if (take > skip) { return take; }
  };
  return skip;
}

LLP-OptimalBinarySearchTree

Optimal binary search tree cost via interval DP: $(i,j)$ is forbidden when $G[i][j]$ is less than the optimal cost over the interval $[i..j]$; the advance sets $G[i][j]$ to the correct value.

// LLP-OptimalBinarySearchTree: ensure G[i][j] >= optimal cost over interval [i..j].

class LLPOptimalBinarySearchTree {
  void LLPOptimalBinarySearchTree(double[] p, double[][] G) {
    forbidden (i, j) : G[i][j] < optCost(p, G, i, j) =>
      advance : G[i][j] = optCost(p, G, i, j);
    // priority: (j - i)
  }

  double optCost(double[] p, double[][] G, int i, int j) {
    double best = infinity;
    int k = i;
    while (k <= j) {
      double s = 0.0;
      int l = i;
      while (l <= j) {
        s = s + p[l];
        l = l + 1;
      }
      double cost = G[i][k-1] + s + G[k+1][j];
      if (cost < best) {
        best = cost;
      }
      k = k + 1;
    }
    return best;
  }
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.