---
title: DP Optimizations
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 9
order: 809
summary: |
  A correct DP recurrence is only half the battle; its naive evaluation is often
  a factor of $n$ slower than necessary. This capstone surveys five techniques,
  monotonic-queue, the convex hull trick, divide-and-conquer optimization,
  Knuth's optimization, and SOS DP, that each exploit _structure in the
  transition_ (a sliding window, linear costs, monotone optimal splits, the
  quadrangle inequality, or subset lattices) to shave an $O(n)$, $O(\log n)$, or
  worse factor off the running time.
topics: [Dynamic Programming]
sources:
  - book: Skiena
    ref: "§ — Dynamic Programming"
  - book: Erickson
    ref: "Ch. — Dynamic Programming"
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming (§15.2, §15.5)"
practice:
  - title: 'Maximum Subarray Sum with One Deletion'
    slug: maximum-subarray-sum-with-one-deletion
    difficulty: Medium
  - title: 'Constrained Subsequence Sum'
    slug: constrained-subsequence-sum
    difficulty: Hard
  - title: 'Jump Game VI'
    slug: jump-game-vi
    difficulty: Medium
  - title: 'Minimum Cost to Cut a Stick'
    slug: minimum-cost-to-cut-a-stick
    difficulty: Hard
  - title: 'Maximum Number of Points with Cost'
    slug: maximum-number-of-points-with-cost
    difficulty: Medium
---

The previous lessons [built DP recurrences](/algorithms/dynamic-programming/principles) and trusted their dimensions to give
the running time: a table of $S$ states, each filled by a transition that scans
$T$ predecessors, costs $O(S \cdot T)$. Often $T$ is itself $\Theta(n)$, a min
over all earlier states or a split point ranging over an interval, and the honest
recurrence runs in $O(n^2)$ or $O(n^3)$. The techniques in this lesson all share
one move: they observe that the transition is not an _arbitrary_ min over
predecessors but one with **structure**, and they maintain an auxiliary object
(a deque, a hull of lines, a monotone split pointer) that answers each transition
faster than a fresh scan.[^cpalg] None of them changes _what_ the DP
computes, only how fast it computes it.

A useful test runs through the whole lesson: look at the shape of the
inner min/max and ask _what stays constant and what slides_ as the outer index
advances. The answer names the technique.

The cost model here is the [state-count times transition-work product](/algorithms/foundations/asymptotic-analysis); these techniques attack the second factor.

## Monotonic-queue optimization

Consider a transition of the form

$$
dp[i] = \parens{\min_{i-k \,\le\, j \,<\, i} dp[j]} + \text{cost}(i),
$$

where each state takes a min (or max) of the previous states _within a sliding
window_ of width $k$, then adds a term depending only on $i$. Evaluated
directly this is $O(nk)$: every state rescans its window. But the window's left
edge only ever moves right, and its right edge only ever moves right, so this is
the **sliding-window minimum** problem, which a **monotonic deque**
solves in $O(1)$ amortized per step.[^skiena]

> **Intuition.** Keep the candidate $dp[j]$ values in a deque sorted in
> increasing order. A new value dominates, and so evicts, every larger value
> already at the back, because that older value can never again be the minimum
> while a smaller, _later_ value survives. The front of the deque is always the
> window's minimum.

```algorithm
caption: $\textsc{MonoQueue-DP}$ — evaluate $dp[i]=\min_{i-k\le j<i}dp[j]+\text{cost}(i)$ in $O(n)$
$Q \gets$ empty deque of indices       // $dp$ increasing front$\to$back
$dp[0] \gets \text{base}$;  push $0$ onto $Q$
for $i \gets 1$ to $n$ do
  while $Q$ nonempty and $front(Q) < i-k$ do
    pop front of $Q$                    // left the window
  $dp[i] \gets dp[front(Q)] + \text{cost}(i)$
  while $Q$ nonempty and $dp[back(Q)] \ge dp[i]$ do
    pop back of $Q$                     // $i$ dominates older candidate
  push $i$ onto $Q$
```

Each index is pushed and popped at most once, so the total work is $O(n)$,
down from $O(nk)$. **Jump Game VI** is the canonical instance: $dp[i]$ is the
best score reachable at index $i$, equal to $\max$ of $dp[j]$ for $j$ in the
last $k$ positions, plus $\text{nums}[i]$: a sliding-window _max_, the same
deque with the inequality flipped. **Constrained Subsequence Sum** is the same
recurrence with $\text{cost}(i)=\text{nums}[i]$ and a $\max(\cdot, 0)$ reset.
This is the [monotonic-stack idea](/algorithms/sequences/monotonic-stacks) from the sequences module, extended to a deque
so that _both_ ends move.

For a full trace, run **Jump Game VI** on
$\text{nums} = [1,\,-1,\,-2,\,4,\,-7,\,3]$ with jump width $k = 2$, so
$dp[i] = \max_{i-2 \le j < i} dp[j] + \text{nums}[i]$ and $dp[0] = 1$. The deque
stores indices whose $dp$ values decrease from front to back; the front is
always the window maximum. Each row shows the state _after_ processing index $i$:

| $i$ | window $[i{-}2, i{-}1]$ | front $dp$ | $dp[i]$ | deque (indices, $dp$) |
|:--:|:--:|:--:|:--:|:--|
| $0$ | — | — | $1$ | $[\,0{:}1\,]$ |
| $1$ | $\{0\}$ | $dp[0]{=}1$ | $1 + (-1) = 0$ | $[\,0{:}1,\ 1{:}0\,]$ |
| $2$ | $\{0,1\}$ | $dp[0]{=}1$ | $1 + (-2) = -1$ | $[\,0{:}1,\ 1{:}0,\ 2{:}{-}1\,]$ |
| $3$ | $\{1,2\}$ | $dp[1]{=}0$ | $0 + 4 = 4$ | $[\,3{:}4\,]$ |
| $4$ | $\{2,3\}$ | $dp[3]{=}4$ | $4 + (-7) = -3$ | $[\,3{:}4,\ 4{:}{-}3\,]$ |
| $5$ | $\{3,4\}$ | $dp[3]{=}4$ | $4 + 3 = 7$ | $[\,5{:}7\,]$ |

Two evictions do the real work. At $i = 3$ index $0$ has slid out of the window
($0 < 3 - 2$), so it is popped from the **front**; then $dp[3] = 4$ dominates the
stale $1{:}0$ and $2{:}{-}1$ at the **back**, clearing them. At $i = 5$ the same
back-eviction wipes $3{:}4$ and $4{:}{-}3$, leaving only the fresh maximum. The
answer $dp[5] = 7$ is read straight off, and across all six steps no index is
touched more than twice.

$$
% caption: a sliding window $[i-k,i-1]$ over the $dp$ row; the deque front holds the
%          window optimum
\begin{tikzpicture}[
  cell/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (a) at (0,0) {$9$};
  \node[cell] (b) at (0.8,0) {$4$};
  \node[cell, draw=acc, very thick] (c) at (1.6,0) {$2$};
  \node[cell] (d) at (2.4,0) {$7$};
  \node[cell] (e) at (3.2,0) {$5$};
  \node[cell] (f) at (4.0,0) {$8$};
  \node[cell, fill=acc!12] (g) at (4.8,0) {$?$};
  % window bracket over c..f
  \draw[acc, thick] (1.2,0.65) -- (1.2,0.5) -- (4.4,0.5) -- (4.4,0.65);
  \node[font=\footnotesize, acc] at (2.8,0.95) {window \texttt{[i-k, i-1]}};
  \node[font=\footnotesize] at (4.8,-0.75) {\texttt{dp[i]}};
  \draw[->, acc] (1.6,-0.7) -- (c.south);
  \node[font=\footnotesize, acc] at (1.6,-0.95) {deque front $=$ min};
\end{tikzpicture}
$$

::impl{algo="monotonic_queue_dp"}

## Convex hull trick

Now suppose each previous state contributes a **line** and the transition queries
the best line at a point:

$$
dp[i] = \min_{j < i}\parens{m_j \cdot x_i + b_j},
$$

where the slope $m_j$ and intercept $b_j$ depend only on $j$ (typically $m_j$ is
a function of $dp[j]$ and the problem data), and $x_i$ depends only on $i$. The
naive evaluation is $O(n^2)$. But $\min_j(m_j x + b_j)$ over a fixed set of lines,
as a function of $x$, is the **lower envelope** of those lines, a convex,
piecewise-linear curve. Only the lines on the **lower hull** can ever be optimal;
the rest are dominated everywhere. Maintaining that hull and querying it is the
**Convex Hull Trick**.[^cpalg]

$$
% caption: each state is a line; the optimal $dp[i]$ is the lower hull queried at $x_i$
\begin{tikzpicture}[>=stealth, scale=0.9]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (-0.2,0) -- (5.2,0) node[right, font=\small] {$x$};
  \draw[->] (0,-0.2) -- (0,3.4);
  % three lines
  \draw (0,3.0) -- (5,0.5);                 % steep down: line A
  \draw (0,1.6) -- (5,1.1);                 % shallow: line B
  \draw (0,0.4) -- (5,2.9);                 % up: line C
  % lower envelope (acc), piecewise A then B then C
  \draw[acc, very thick] (0,1.6) -- (1.5,1.45) -- (3.4,1.78) -- (5,2.9);
  % query
  \draw[dashed] (2.4,0) -- (2.4,1.66);
  \node[font=\footnotesize] at (2.4,-0.28) {$x_i$};
  \fill[acc] (2.4,1.66) circle (1.6pt);
  \node[font=\footnotesize, acc] at (3.9,0.55) {lower hull};
  \node[font=\footnotesize, fill=white, inner sep=1.5pt] at (4.4,3.1) {lines};
\end{tikzpicture}
$$

If lines are inserted in monotone slope order and queries $x_i$ are also
monotone, both operations are $O(1)$ amortized: push lines onto a stack-like
hull, popping any that the newcomer makes redundant, and advance a pointer for
queries. Without monotonicity, store the hull and binary-search for the optimal
line at $x_i$ in $O(\log n)$, or use a Li Chao tree. Either way the DP drops from
$O(n^2)$ to $O(n\log n)$.

> **Remark (When it applies).** The transition must be _linear in a value $x_i$ that
> depends only on $i$_, with the slope and intercept depending only on $j$. The
> classic trigger is a cost that factors as a product $a_j \cdot b_i$ after
> expanding a square, e.g. partitioning costs of the form $(\text{prefix} \cdot
> \text{value})$, which appear in build/print problems and 1-D clustering.

For example, suppose
three previous states have contributed the lines $\ell_0(x) = x + 3$,
$\ell_1(x) = 4$, and $\ell_2(x) = -x + 6$ (slopes $+1$, $0$, $-1$). Their lower
envelope, the pointwise minimum, is a convex $\vee$ shape. Checking crossings,
$\ell_0 = \ell_2$ at $x + 3 = -x + 6 \Rightarrow x = \tfrac32$, where both equal
$4.5$. But the flat line $\ell_1 = 4$ already sits _below_ that meeting point, so
$\ell_0$ and $\ell_2$ never touch the envelope near their crossing: $\ell_1$
undercuts both. Solving $\ell_0 = \ell_1$ gives $x = 1$ and $\ell_1 = \ell_2$
gives $x = 2$, so the envelope is $\ell_0$ on $(-\infty, 1]$, then $\ell_1$ on
$[1, 2]$, then $\ell_2$ on $[2, \infty)$ — all three lines survive on the hull.
For a query $x_i = 1.5$ the naive scan evaluates all three ($\ell_0 = 4.5$,
$\ell_1 = 4$, $\ell_2 = 4.5$) and takes the min, $4$. With monotone queries the
hull instead advances a pointer to the $\ell_1$ segment and reads $4$ in $O(1)$,
never re-checking $\ell_0$ or $\ell_2$. Had $\ell_1$ been $\ell_1 = 5$ instead,
the two crossings would invert ($\ell_0 = \ell_1$ at $x = 2$, $\ell_1 = \ell_2$
at $x = 1$) and $\ell_1$ would be dominated everywhere; inserting it would find
it already redundant and **pop** it, leaving the two-line hull $\{\ell_0,
\ell_2\}$ meeting at $x = \tfrac32$.

::impl{algo="convex_hull_trick"}

## Divide-and-conquer optimization

For a layered transition

$$
dp[i][j] = \min_{k < j}\parens{dp[i-1][k] + C(k, j)},
$$

let $opt(i,j)$ be the smallest $k$ achieving that minimum. If $opt$ is
**monotone in $j$** (that is, $opt(i,j) \le opt(i, j+1)$ for every fixed layer $i$),
then the search range for column $j$ is bounded by the answers of its neighbors,
and we can solve a whole layer by divide and conquer:

```algorithm
caption: $\textsc{DC-Opt}(i, j_{lo}, j_{hi}, k_{lo}, k_{hi})$ — fill layer $i$, columns $[j_{lo},j_{hi}]$
if $j_{lo} > j_{hi}$ then return
$j_{mid} \gets \lfloor (j_{lo}+j_{hi})/2 \rfloor$
$best \gets \infty$;  $opt \gets k_{lo}$
for $k \gets k_{lo}$ to $\min(j_{mid}-1,\,k_{hi})$ do
  if $dp[i-1][k] + C(k,j_{mid}) < best$ then
    $best \gets dp[i-1][k] + C(k,j_{mid})$;  $opt \gets k$
$dp[i][j_{mid}] \gets best$
$\textsc{DC-Opt}(i,\ j_{lo},\ j_{mid}-1,\ k_{lo},\ opt)$
$\textsc{DC-Opt}(i,\ j_{mid}+1,\ j_{hi},\ opt,\ k_{hi})$
```

Solve the middle column $j_{mid}$ first by scanning its full allowed $k$-range;
its optimum $opt$ then **caps** the left half's search and **floors** the right
half's, so the two recursive calls split both the columns and the candidate range:

$$
% caption: Divide-and-conquer optimization. Solving $j_{mid}$ finds $opt(j_{mid})$; by
%          monotonicity the left columns search only $[k_{lo},opt]$ and the right only
%          $[opt,k_{hi}]$, halving the column span while the $k$-ranges overlap only at
%          $opt$.
\begin{tikzpicture}[
  >=stealth, every node/.style={font=\footnotesize},
  jbar/.style={draw, minimum height=6mm, fill=acc!12, inner sep=2pt},
  kbar/.style={draw, minimum height=6mm, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  % column axis (top): jlo .. jmid .. jhi
  \node[anchor=east] at (-1.15,1.4) {columns $j$:};
  \node[jbar, inner sep=3pt] (jl) at (0.1,1.4) {\texttt{[jlo, jmid-1]}};
  \node[draw, fill=acc!15, draw=acc, very thick, minimum height=6mm, inner sep=3pt] (jm) at (2.5,1.4) {\texttt{jmid}};
  \node[jbar, inner sep=3pt] (jr) at (4.9,1.4) {\texttt{[jmid+1, jhi]}};
  % k-range axis (bottom): klo .. opt .. khi
  \node[anchor=east] at (-1.15,-0.6) {candidates $k$:};
  \node[kbar, inner sep=3pt] (kl) at (0.4,-0.6) {\texttt{[klo, opt]}};
  \node[kbar, inner sep=3pt] (kr) at (4.9,-0.6) {\texttt{[opt, khi]}};
  \node[draw=none, acc] at (2.3,-0.6) {\texttt{opt}};
  % opt tick joining jmid to the shared boundary of the two k-ranges
  \draw[->, red!75!black, thick] (jm.south) -- node[right, font=\footnotesize, red!75!black]{solve, get \texttt{opt}} (2.3,-0.32);
  % which column-half searches which k-range
  \draw[->, acc] (jl.south) to[out=-90,in=90] (kl.north);
  \draw[->, acc] (jr.south) to[out=-90,in=90] (kr.north);
\end{tikzpicture}
$$

At each recursion depth the $k$-ranges across all sub-calls overlap by at most
their endpoints, so one depth costs $O(n)$; there are $O(\log n)$ depths per
layer and $O(k)$ layers, giving $O(kn\log n)$ instead of $O(kn^2)$. The
monotonicity of $opt$ is the hypothesis you must verify; it holds whenever $C$
satisfies the quadrangle inequality (below), but is sometimes provable directly
from the problem.

::impl{algo="divide_and_conquer_dp"}

## Knuth's optimization

Interval DPs have the shape

$$
dp[i][j] = \min_{i \le k < j}\parens{dp[i][k] + dp[k+1][j]} + C(i, j),
$$

and naively cost $O(n^3)$: $O(n^2)$ intervals, each scanning $O(n)$ split points.
**Knuth's optimization** applies when $C$ satisfies the **quadrangle inequality**
(QI) and is monotone on intervals:

> **Definition (Quadrangle inequality).** For all $a \le b \le c \le d$,
> $$C(a,c) + C(b,d) \;\le\; C(a,d) + C(b,c).$$

When QI holds, the optimal split point is monotone in _both_ arguments:

$$
opt[i][j-1] \;\le\; opt[i][j] \;\le\; opt[i+1][j].
$$

So when filling $dp[i][j]$ we only scan split points $k$ in
$\brackets{\,opt[i][j-1],\ opt[i+1][j]\,}$ rather than all of $[i, j)$.
Summed over a fixed interval length, those ranges telescope, and the total work
collapses to $O(n^2)$. This is the optimization behind **optimal binary search
trees** and the cost-merging part of **matrix-chain multiplication** from the
[interval-DP lesson](/algorithms/dynamic-programming/interval-dp): both have cost functions satisfying QI, so Knuth's
optimization applies and each runs in $O(n^2)$.

$$
% caption: Knuth's optimization: filling $dp[i][j]$ scans only
%          $k\in[\,opt[i][j-1],\,opt[i+1][j]\,]$, a window pinned by two already-known
%          optimal splits, not all of $[i,j)$
\begin{tikzpicture}[
  cell/.style={draw, minimum size=8mm, inner sep=1pt, font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \x/\lab in {0/i,1/{},2/{},3/{},4/{},5/{},6/{j}} {
    \node[cell] (k\x) at (\x*0.9,0) {$\lab$};
  }
  \node[cell, fill=black!8] at (2*0.9,0) {};
  \node[cell, fill=acc!18] at (3*0.9,0) {};
  \node[cell, fill=acc!18] at (4*0.9,0) {};
  \node[cell, fill=black!8] at (5*0.9,0) {};
  \draw[acc, thick] (2*0.9-0.45,0.62) -- (2*0.9-0.45,0.5) -- (5*0.9+0.45,0.5) -- (5*0.9+0.45,0.62);
  \node[font=\footnotesize, acc] at (3.5*0.9,1.0) {scan only this window};
  \node[font=\footnotesize] at (2*0.9,-0.78) {\texttt{opt[i][j-1]}};
  \node[font=\footnotesize] at (5*0.9,-0.78) {\texttt{opt[i+1][j]}};
  \node[font=\footnotesize] at (3.5*0.9,-1.5) {split candidates $k$};
\end{tikzpicture}
$$

::impl{algo="knuth_optimization"}

## SOS DP (sum over subsets)

The last technique is combinatorial rather than geometric. Given a value $f[m]$
for every bitmask $m$ over $n$ bits, we want, for each mask $m$, an aggregate
over all of its **submasks**:

$$
g[m] = \sum_{s \subseteq m} f[s].
$$

Enumerating every submask of every mask costs $\sum_m 2^{\text{popcount}(m)} =
3^n$ (the classic submask-enumeration bound). **Sum over subsets** does it in
$O(n\,2^n)$ by adding _one bit-dimension at a time_: process bits $0..n-1$, and
when processing bit $b$, fold each mask that has bit $b$ set into the version
without it. It is a multidimensional [prefix sum](/algorithms/sequences/prefix-sums) over the hypercube $\{0,1\}^n$.

$$
% caption: SOS DP folds one bit at a time over the hypercube $\{0,1\}^3$: when processing
%          bit $b$, each mask with bit $b$ set absorbs $g[m\oplus(1{\ll}b)]$ along that
%          axis
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=0, font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (000) at (0,0) {$000$};
  \node (001) at (2.6,0) {$001$};
  \node (010) at (0,2.6) {$010$};
  \node (011) at (2.6,2.6) {$011$};
  \node (100) at (1.3,1.1) {$100$};
  \node (101) at (3.9,1.1) {$101$};
  \node (110) at (1.3,3.7) {$110$};
  \node (111) at (3.9,3.7) {$111$};
  \draw[->, acc, thick] (000) -- (001);
  \draw[->, acc, thick] (010) -- (011);
  \draw[->, acc, thick] (100) -- (101);
  \draw[->, acc, thick] (110) -- (111);
  \draw (000) -- (010); \draw (001) -- (011);
  \draw (000) -- (100); \draw (001) -- (101);
  \draw (010) -- (110); \draw (011) -- (111);
  \draw (100) -- (110); \draw (101) -- (111);
  \draw (100) -- (101);
  \node[draw=none, font=\footnotesize, acc] at (2.0,-0.9) {fold bit 0: \texttt{g[m] += g[m XOR 1]}};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{SOS}$ — submask sums for all masks in $O(n\,2^n)$
for $m \gets 0$ to $2^n-1$ do
  $g[m] \gets f[m]$
for $b \gets 0$ to $n-1$ do
  for $m \gets 0$ to $2^n-1$ do
    if $m \mathbin{\&} (1 \ll b) \ne 0$ then
      $g[m] \gets g[m] + g[m \oplus (1 \ll b)]$
```

After processing bit $b$, $g[m]$ holds the sum of $f$ over all submasks of $m$
that differ from $m$ only in bits $0..b$; after all $n$ bits, it is the full
submask sum. To see the fold in motion, take $n = 3$ with
$f = [1, 2, 3, 4, 5, 6, 7, 8]$ indexed by masks $000 \dots 111$. The array $g$
starts as a copy of $f$ and absorbs one axis per pass:

| after | $000$ | $001$ | $010$ | $011$ | $100$ | $101$ | $110$ | $111$ |
|:--|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| init | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
| bit $0$ | $1$ | $3$ | $3$ | $7$ | $5$ | $11$ | $7$ | $15$ |
| bit $1$ | $1$ | $3$ | $4$ | $10$ | $5$ | $11$ | $12$ | $26$ |
| bit $2$ | $1$ | $3$ | $4$ | $10$ | $6$ | $14$ | $16$ | $36$ |

The final row is the submask sum. Check $g[111] = 1+2+3+4+5+6+7+8 = 36$ (all
eight submasks) and $g[101] = f[000]+f[001]+f[100]+f[101] = 1+2+5+6 = 14$, both
matching the table — computed in $3 \cdot 2^3 = 24$ additions rather than the
$3^3 = 27$ of naive submask enumeration, a gap that widens fast: at $n = 20$ it is
$2 \times 10^7$ against $3.5 \times 10^9$.

Replacing the order of the two loops, or flipping the bit test,
gives sums over _supersets_ instead. This is what drives the
**bitmask-DP** lesson's harder counting problems: anything that asks you to
aggregate over all subsets of every state at once.

::impl{algo="sos_dp"}

## Choosing the technique

| Technique | Transition shape | Complexity win |
| --- | --- | --- |
| Monotonic queue | $dp[i]=\min_{i-k\le j<i} dp[j]+\text{cost}(i)$ (sliding window) | $O(nk)\to O(n)$ |
| Convex hull trick | $dp[i]=\min_j(m_j x_i + b_j)$ (line per state) | $O(n^2)\to O(n\log n)$ |
| Divide & conquer | $dp[i][j]=\min_{k<j} dp[i-1][k]+C(k,j)$, $opt$ monotone | $O(kn^2)\to O(kn\log n)$ |
| Knuth | $dp[i][j]=\min_{i\le k<j}(dp[i][k]+dp[k{+}1][j])+C(i,j)$, QI | $O(n^3)\to O(n^2)$ |
| SOS DP | $g[m]=\bigoplus_{s\subseteq m} f[s]$ (submask aggregate) | $O(3^n)\to O(n\,2^n)$ |

## The origins of the speedups

Each technique here has a traceable pedigree, and the pedigrees explain why the
conditions are what they are. **Knuth's optimization** is the oldest: Donald
Knuth's 1971 paper "Optimum binary search trees" (_Acta Informatica_ 1) showed
that the $O(n^3)$ dynamic program for optimal BSTs runs in $O(n^2)$ because the
optimal root of the interval $[i, j]$ lies between the optimal roots of $[i,
j{-}1]$ and $[i{+}1, j]$. F. Frances Yao generalized the mechanism in "Efficient
dynamic programming using quadrangle inequalities" (1980, STOC) and "Speed-up in
dynamic programming" (1982, _SIAM J. Algebraic Discrete Methods_), isolating the
**quadrangle inequality** as the exact structural hypothesis, which is why the
condition carries her name (the Knuth\/Yao QI) and covers matrix-chain and BST
alike.[^knuth-yao]

The **convex hull trick** grew out of computational geometry's lower-envelope
machinery rather than a single DP paper; the general offline\/online line-container
that supports arbitrary insertion order is the **Li Chao tree** (attributed to the
competitive-programming author Li Chao), a segment tree over $x$-coordinates that
stores at each node the line best there, answering point queries in $O(\log n)$
without any slope-monotonicity assumption. **Divide-and-conquer optimization** is
the algorithmic cousin of the same monotone-optimum idea; it needs only that
$opt(i, j)$ be monotone in $j$, a strictly weaker condition than the full QI, which
is why it applies to layered ("exactly $k$ groups") partition DPs where Knuth does
not.

**Sum-over-subsets** is a special case of the **fast zeta / Möbius transform** over
the subset lattice, the combinatorial analog of the fast Fourier transform for the
Boolean hypercube. Björklund, Husfeldt, Kaski, and Koivisto's work on subset
convolution ("Fourier meets Möbius: fast subset convolution", 2007, STOC) built on
exactly this $O(n\,2^n)$ zeta transform to compute the full subset convolution in
$O(n^2 2^n)$, which in turn cracked several $\#P$-flavored counting problems and the
graph-coloring polynomial.[^subsetconv] The monotonic-deque idea, meanwhile, is the sliding-window
minimum, folklore since at least the 1980s and standard in streaming and signal
processing (it is the linear-time morphological erosion of a 1-D signal). Modern
competitive programming (see the open **cp-algorithms** reference) collects all
five together because they answer one question — _what structure does the
inner loop have?_ — with the same discipline the [asymptotic-analysis
lesson](/algorithms/foundations/asymptotic-analysis) applies to loops in general.

## Takeaways

- These are not new DPs but **faster evaluations** of an existing recurrence;
  the trigger is always _structure in the inner min/max_, not its mere size.
- **Monotonic-queue optimization**: a sliding-window min/max transition runs in
  $O(n)$ via a **monotonic deque** whose front is the window optimum — the
  natural tool for Jump Game VI and Constrained Subsequence Sum.
- **Convex hull trick**: when each state is a _line_ and the transition queries
  the **lower envelope** at $x_i$, maintain the hull and query in $O(\log n)$
  (or $O(1)$ amortized when slopes and queries are monotone), turning $O(n^2)$
  into $O(n\log n)$.
- **Divide-and-conquer optimization** needs a **monotone optimal split**
  $opt(i,j)$; **Knuth's optimization** gets that monotonicity for interval DPs
  from the **quadrangle inequality**, dropping $O(n^3)$ to $O(n^2)$ on problems
  like optimal BST and matrix-chain.
- **SOS DP** aggregates over every submask of every mask in $O(n\,2^n)$ by
  summing one bit-dimension at a time — a prefix sum over the subset lattice.
- Verify the **applicability condition** (window monotonicity, linear cost,
  monotone split, QI) before reaching for the speedup; the optimization is only
  correct when its structural hypothesis holds.

[^cpalg]: **Erickson**, Ch. — Dynamic Programming: DP optimizations (the convex hull trick, divide-and-conquer, and Knuth's optimization) treated as transition-acceleration techniques over a fixed recurrence; **CLRS** §15.2/§15.5 for the interval-DP instances (matrix-chain, optimal BST) that Knuth accelerates.
[^skiena]: **Skiena**, § — Dynamic Programming: recognizing that a DP's cost is the product of state count and per-state transition work, and attacking the transition.
[^knuth-yao]: **Knuth**, "Optimum binary search trees", _Acta Informatica_ 1 (1971), and **F. F. Yao**, "Speed-up in dynamic programming", _SIAM J. Algebraic Discrete Methods_ 3 (1982): the $O(n^2)$ optimal-BST algorithm and the quadrangle-inequality generalization behind Knuth's optimization.
[^subsetconv]: **Björklund, Husfeldt, Kaski, Koivisto**, "Fourier meets Möbius: fast subset convolution", STOC 2007: the fast zeta/Möbius transform over the subset lattice ($O(n\,2^n)$) that SOS DP computes, and its use in $O(n^2 2^n)$ subset convolution.