DP Optimizations

The previous lessons built DP recurrences 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 $Θ (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.¹ 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; these techniques attack the second factor.

Monotonic-queue optimization

Consider a transition of the form

d p [i] = (min_{i - k \leq j < i} d p [j]) + 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 exactly the sliding-window minimum problem, which a monotonic deque solves in $O (1)$ amortized per step.²

Algorithm:

\textsc{MonoQueue-DP}

— evaluate

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

O(n)

1
$Q \gets$ empty deque of indices
$dp$ increasing front $\to$ back
2
$dp[0] \gets \text{base}$ ; push $0$ onto $Q$
3
for $i \gets 1$ to $n$ do
4
while $Q$ nonempty and $front(Q) < i-k$ do
5
pop front of $Q$
left the window
6
$dp[i] \gets dp[front(Q)] + \text{cost}(i)$
7
while $Q$ nonempty and $dp[back(Q)] \ge dp[i]$ do
8
pop back of $Q$
$i$ dominates older candidate
9
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: $d p [i]$ is the best score reachable at index $i$ , equal to $max$ of $d p [j]$ for $j$ in the last $k$ positions, plus $nums [i]$ : a sliding-window max, the same deque with the inequality flipped. Constrained Subsequence Sum is the same recurrence with $cost (i) = nums [i]$ and a $max (\cdot, 0)$ reset. This is the monotonic-stack idea from the sequences module, extended to a deque so that both ends move.

a sliding window

[i - k, i - 1]

over the

d p

row; the deque front holds the window optimum

Convex hull trick

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

d p [i] = min_{j < i} (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 $d p [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.¹

each state is a line; the optimal

d p [i]

is the lower hull queried at

x_{i}

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)$ .

Divide-and-conquer optimization

For a layered transition

d p [i] [j] = min_{k < j} (d p [i - 1] [k] + C (k, j)),

let $o pt (i, j)$ be the smallest $k$ achieving that minimum. If $o pt$ is monotone in $j$ (that is, $o pt (i, j) \leq o pt (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:

\textsc{DC-Opt}(i, j_{lo}, j_{hi}, k_{lo}, k_{hi})

— fill layer

i

, columns

[j_{lo},j_{hi}]

1
if $j_{lo} > j_{hi}$ then return
2
$j_{mid} \gets \lfloor (j_{lo}+j_{hi})/2 \rfloor$
3
$best \gets \infty$ ; $opt \gets k_{lo}$
4
for $k \gets k_{lo}$ to $\min(j_{mid}-1,\,k_{hi})$ do
5
if $dp[i-1][k] + C(k,j_{mid}) < best$ then
6
$best \gets dp[i-1][k] + C(k,j_{mid})$ ; $opt \gets k$
7
$dp[i][j_{mid}] \gets best$
8
$\textsc{DC-Opt}(i,\ j_{lo},\ j_{mid}-1,\ k_{lo},\ opt)$
9
$\textsc{DC-Opt}(i,\ j_{mid}+1,\ j_{hi},\ opt,\ k_{hi})$

Solve the middle column $j_{mi d}$ first by scanning its full allowed $k$ -range; its optimum $o pt$ 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:

Divide-and-conquer optimization. Solving

j_{mi d}

finds

o pt (j_{mi d})

; by monotonicity the left columns search only

[k_{l o}, o pt]

and the right only

[o pt, k_{hi}]

, halving the column span while the

k

-ranges overlap only at

o pt

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 (k n log n)$ instead of $O (k n^{2})$ . The monotonicity of $o pt$ is the hypothesis you must verify; it holds whenever $C$ satisfies the quadrangle inequality (below), but is sometimes provable directly from the problem.

Knuth's optimization

Interval DPs have the shape

d p [i] [j] = min_{i \leq k < j} (d p [i] [k] + d p [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:

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

o pt [i] [j - 1] \leq o pt [i] [j] \leq o pt [i + 1] [j] .

So when filling $d p [i] [j]$ we only scan split points $k$ in $[o pt [i] [j - 1], o pt [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: both have cost functions satisfying QI, so each yields to Knuth and runs in $O (n^{2})$ .

Knuth's optimization: filling

d p [i] [j]

scans only

k \in [o pt [i] [j - 1], o pt [i + 1] [j]]

, a window pinned by two already-known optimal splits, not all of

[i, j)

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] = s \subseteq m \sum f [s] .

Enumerating every submask of every mask costs $\sum_{m} 2^{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 over the hypercube ${0, 1}^{n}$ .

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 ≪ b)]

along that axis

Algorithm:

\textsc{SOS}

— submask sums for all masks in

O(n\,2^n)

1
for $m \gets 0$ to $2^n-1$ do
2
$g[m] \gets f[m]$
3
for $b \gets 0$ to $n-1$ do
4
for $m \gets 0$ to $2^n-1$ do
5
if $m \mathbin{\&} (1 \ll b) \ne 0$ then
6
$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. 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.

Choosing the technique

Technique	Transition shape	Complexity win
Monotonic queue	$d p [i] = min_{i - k \leq j < i} d p [j] + cost (i)$ (sliding window)	$O (nk) \to O (n)$
Convex hull trick	$d p [i] = min_{j} (m_{j} x_{i} + b_{j})$ (line per state)	$O (n^{2}) \to O (n log n)$
Divide & conquer	$d p [i] [j] = min_{k < j} d p [i - 1] [k] + C (k, j)$ , $o pt$ monotone	$O (k n^{2}) \to O (k n log n)$
Knuth	$d p [i] [j] = min_{i \leq k < j} (d p [i] [k] + d p [k + 1] [j]) + C (i, j)$ , QI	$O (n^{3}) \to O (n^{2})$
SOS DP	$g [m] = ⨁_{s \subseteq m} f [s]$ (submask aggregate)	$O (3^{n}) \to O (n 2^{n})$

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 $o pt (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.

CP-Algorithms, — DP optimizations: the convex hull trick, divide-and-conquer, and Knuth optimizations treated as transition-acceleration techniques over a fixed recurrence. ↩ ↩²
Skiena, § — Dynamic Programming: recognizing that a DP's cost is the product of state count and per-state transition work, and attacking the transition. ↩

Monotonic-queue optimization

Convex hull trick

Divide-and-conquer optimization

Knuth's optimization

SOS DP (sum over subsets)

Choosing the technique

Takeaways

Footnotes