1. Introduction & Motivation
This is Part 2 of a two-part pairing on DP-transition acceleration. Part 1: Monotonic Queue, Divide & Conquer, and Knuth Optimization covered techniques that exploit monotonicity: as $i$ grows, the optimal $j$ that minimizes $dp[i]$ only moves forward, so a sliding window, a divide-and-conquer split, or Knuth's quadrangle inequality can skip transitions that monotonicity proves can never win.
That argument works when the optimal decision point is monotone in $i$. But plenty of transitions have a cost function whose shape -- not its monotonicity -- is the exploitable structure. This lesson covers three such shapes:
- Convexity: when $dp[i] = \min_j\big(dp[j] + b[j]\cdot a[i]\big)$, each $j$ defines a line $y = b[j]x + dp[j]$, and the transition is really "evaluate the lower envelope of these lines at $x=a[i]$." The Convex Hull Trick (and its dynamic cousin, the Li Chao Tree) maintain that envelope directly.
- The Monge property: a matrix-shaped cost function that satisfies the same quadrangle inequality as Knuth optimization, but reframed as a property of an entire $n\times m$ cost matrix. SMAWK exploits it to compute every row's minimum in linear total time, not quadratic.
- A tunable penalty: when the real problem asks for "minimum cost using exactly $k$ operations," but only the unconstrained "any number of operations" version is fast, the Aliens Trick (Lagrangian relaxation / WQS binary search) trades the hard count constraint for a binary search over a penalty term.
None of these three techniques requires the other two, and none requires Part 1's monotonicity argument -- but all three answer the same higher-level question Part 1 raised: once you've written the $O(n^2)$ (or $O(nk)$) transition, what property of the cost function lets you compute it faster?
2. Prerequisites
This lesson assumes comfort with basic dynamic programming transitions, arrays, and recursion -- see Part 14: Dynamic Programming Foundations for the state/transition/base-case framing this lesson builds on. It also assumes the general "accelerating a DP transition" mindset introduced in Part 1: Monotonic Queue, Divide & Conquer & Knuth Optimization: writing the naive $O(n^2)$ transition first, then asking what property of the cost function makes most of those $O(n^2)$ comparisons redundant. Part 1 is not a hard dependency for the algorithms themselves, but its vocabulary (quadrangle inequality, decision monotonicity) is used here by comparison.
3. Convex Hull Trick: Core Insight
Many DP transitions reduce to the form:
$$dp[i] = \min_{j \lt i}\Big(dp[j] + b[j]\cdot a[i]\Big)$$
Fix $j$ and look at this as a function of $x = a[i]$: it is a line, $y = b[j]\cdot x + dp[j]$, with slope $b[j]$ and intercept $dp[j]$. Computing $dp[i]$ means evaluating every line $j \lt i$ at $x = a[i]$ and keeping the minimum -- exactly the $O(n)$-per-query naive approach, $O(n^2)$ overall.
The Convex Hull Trick maintains this envelope as a stack (or deque) of surviving lines. Two rules make it work:
- Insertion order: if lines are added in order of monotonically decreasing slope, a new line can only ever displace lines at the end of the current envelope -- never in the middle. This lets insertion use a simple stack instead of a general search structure.
- Popping irrelevant lines: when a new line is added, check whether the second-to-last line in the stack is ever optimal anywhere given its neighbors. If the new line and the line before the second-to-last already cross at an $x$ no larger than where the second-to-last line would have started winning, the second-to-last line never wins against both of its neighbors and can be discarded. This check repeats until the stack stabilizes.
Once the envelope is built, a query for the minimum at a given $x$ is a search over the envelope's lines. If queries also arrive in monotonically increasing (or decreasing) $x$ order, a single forward-moving pointer answers all queries in amortized $O(1)$ total. If queries arrive in arbitrary order, a binary search over the envelope (which is sorted by slope, and therefore by winning interval) answers each query in $O(\log n)$.
4. A Concrete Example for the Convex Hull Trick
Building the lower envelope, one pop included
Add four lines in decreasing slope order: $L_1: y=3x$, $L_2: y=x+3$, $L_3: y=-x+9$, $L_4: y=-3x+11$.
| Step | Line added | Envelope before check | Pop? | Envelope after |
|---|---|---|---|---|
| 1 | $L_1: y=3x$ | [ ] | too few lines to check | [$L_1$] |
| 2 | $L_2: y=x+3$ | [$L_1$] | too few lines to check | [$L_1$, $L_2$] |
| 3 | $L_3: y=-x+9$ | [$L_1$, $L_2$] | no -- $L_2$ still wins somewhere | [$L_1$, $L_2$, $L_3$] |
| 4 | $L_4: y=-3x+11$ | [$L_1$, $L_2$, $L_3$] | yes -- $L_3$ is popped | [$L_1$, $L_2$, $L_4$] |
Why does $L_3$ get popped? $L_2$ and $L_3$ cross at $x=3$ (both equal $6$), and $L_2$ and $L_4$ cross at $x=2$ (both equal $5$). Since the $L_2$/$L_4$ crossing happens before the $L_2$/$L_3$ crossing, $L_4$ overtakes $L_2$ while $L_2$ is still beating $L_3$ -- so $L_3$ never gets a chance to be the minimum against both neighbors and is safe to discard.
Querying the final envelope [$L_1$, $L_2$, $L_4$] at a few points confirms it: at $x=0$, $L_1=0$ is smallest; at $x=2$, $L_2=5$ and $L_4=5$ tie (their crossing point); at $x=4$, $L_4=-1$ is smallest. The discarded line $L_3$ would have given $5$ at $x=4$ -- never the minimum, exactly as predicted.
5. Convex Hull Trick Implementation (Monotone Case)
The classic application is a DP where the cost of "jumping" from index $j$ to index $i$ is a squared difference: $dp[i] = \min_{j\lt i}\big(dp[j] + (h[i]-h[j])^2\big)$ for a strictly increasing sequence $h$. Expanding the square:
$$dp[i] = \min_{j\lt i}\Big(dp[j] + h[j]^2 - 2h[j]\cdot h[i]\Big) + h[i]^2$$
Each $j$ contributes a line with slope $-2h[j]$ and intercept $dp[j]+h[j]^2$, evaluated at $x=h[i]$. Because $h$ is increasing, the slopes $-2h[j]$ are automatically added in decreasing order and the queries $x=h[i]$ automatically arrive in increasing order -- the monotone case applies with no extra sorting.
Li Chao Tree: The Dynamic/Non-Monotone Case
The monotone Convex Hull Trick needs both lines and queries to arrive in a cooperative order. Many problems don't offer that: slopes may be inserted in arbitrary order, and queries may be interleaved with insertions in arbitrary order too. The Li Chao Tree handles this generally, at the cost of $O(\log n)$ per operation instead of amortized $O(1)$.
A Li Chao Tree is a segment tree over the $x$-coordinate domain (the same mechanics covered in Segment Tree Variants and the Union-Find, Trie & Segment Tree decision guide -- this section does not re-derive segment-tree basics, only the twist specific to lines). Each node owns a range of $x$-values and stores the single line that is currently "winning" somewhere in that range. Inserting a new line compares it against the node's current line at the range's left endpoint and midpoint: if the new line wins at the midpoint, it replaces the stored line (and the old line is pushed down to recurse into whichever half it might still win); if the new line only wins on one side of the midpoint, it recurses into that half directly. Querying a point walks root-to-leaf, taking the best value seen at each node along the way.
6. Monge Arrays and Totally Monotone Matrices
A Monge matrix is automatically totally monotone: if $\text{argmin}_c\, M[r][c]$ denotes the column holding row $r$'s minimum, then $\text{argmin}_c\, M[r][c]$ is non-decreasing as $r$ increases. Intuitively, the quadrangle inequality says that moving to a later row never makes an earlier column look relatively better -- so the row-minimizing column can only drift rightward.
Why this matters: naively computing the minimum of every row of an $n\times m$ matrix costs $O(nm)$. If the matrix is totally monotone, SMAWK (Shor, Moran, Aggarwal, Wilber, Klawe) computes every row's minimum in only $O(n+m)$ total matrix accesses -- without ever materializing the matrix -- using two cooperating phases:
- Reduce: discard columns that can never be a row-minimum for any row. Scan columns left to right, maintaining a stack of survivors capped at (at most) one column per row: while the top survivor loses to the incoming column at the row matching the survivor's position, pop it (it is dominated); otherwise the incoming column joins the stack. This mirrors a monotone-stack argument and leaves at most $\min(n, m)$ candidate columns.
- Interpolate: recursively solve the same problem restricted to only the odd-indexed rows against the reduced columns. Because total monotonicity guarantees the answer columns are non-decreasing across all rows (not just the odd ones), each even-indexed row's answer column must lie between its two odd-indexed neighbors' answer columns -- so each even row only needs a short linear scan bounded by that window, not a scan of every reduced column.
The recursion halves the number of rows each level (odd rows recurse, even rows interpolate), giving $O(n)$ total interpolation work across $O(\log n)$ levels, plus $O(m)$ total reduce work -- $O(n+m)$ overall.
Row minima without building the matrix
Let $a=[1,2,5]$ (rows) and $b=[0,3,4,10]$ (columns), with $\text{cost}(i,j) = (a_i - b_j)^2$ -- a classic Monge cost function. The full matrix, if you materialized it, would be:
| $b_0=0$ | $b_1=3$ | $b_2=4$ | $b_3=10$ | |
|---|---|---|---|---|
| $a_0=1$ | 1 | 4 | 9 | 81 |
| $a_1=2$ | 4 | 1 | 4 | 64 |
| $a_2=5$ | 25 | 4 | 1 | 25 |
The row-minimizing column is $0, 1, 2$ for rows $0, 1, 2$ -- non-decreasing, as total monotonicity guarantees. SMAWK finds these three answers using only $O(n+m)=O(7)$ matrix accesses (up to constants), never comparing every one of the $12$ entries.
7. The Aliens Trick (Lagrangian Relaxation / WQS Binary Search)
Why does this work? As $\lambda$ increases, using more operations becomes more expensive, so the operation count the unconstrained solver "wants" to use is non-increasing in $\lambda$. This only produces a correct answer when the true cost-as-a-function-of-$k$ curve is convex -- each additional operation buys a diminishing (but still non-negative) reduction in cost. Concretely: fix $\lambda$, solve $g(\lambda) = \min_{\text{any } t}\big(\text{cost}(t \text{ operations}) + \lambda t\big)$, and if the achieving $t$ equals $k$, then $\text{cost}(k) = g(\lambda) - \lambda k$ -- the penalty term cancels out exactly.
The concrete example here is "partition an array into exactly $k$ contiguous segments, minimizing the sum of each segment's squared sum." The unconstrained inner DP is $g[i] = \min_{j\lt i}\big(g[j] + \text{cost}(j,i) + \lambda\big)$, which drops the extra count dimension; a binary search over $\lambda$ recovers the exactly-$k$ answer.
8. Complexity Analysis
SMAWK: $O(n+m)$ total matrix accesses for an implicitly-defined $n\times m$ totally monotone matrix, versus $O(nm)$ for the naive per-row scan.
Aliens Trick: adds an $O(\log(\text{range of } \lambda))$ multiplicative factor on top of whatever the unconstrained DP already costs -- if the unconstrained DP is $O(n)$ or $O(n\log n)$ per evaluation, the constrained exactly-$k$ answer costs $O(n\log(\text{range}))$ or $O(n\log n\log(\text{range}))$ overall, instead of paying an extra factor of $k$ for a count dimension.
All three techniques share a theme: they turn a factor that looks unavoidable in the naive transition -- checking every $j$, scanning every column, tracking every possible count -- into a factor that the cost function's own structure lets you skip.
9. Applications & Alternatives
Where these techniques show up
- Convex Hull Trick / Li Chao Tree: task scheduling with per-batch linear costs, "minimum cost to reach the end" problems with quadratic transition costs, and any DP where the transition is literally a line evaluated at a query point.
- SMAWK: optimal binary search tree construction, least-weight subsequence problems, and any DP whose transition cost matrix satisfies the quadrangle inequality but doesn't fit neatly into Knuth's single-recurrence framing.
- Aliens Trick: "choose exactly $k$" variants of segment-partitioning problems, tree problems requiring exactly $k$ selected edges or nodes, and any problem where the unconstrained version is fast but a hard count constraint seems to demand an extra DP dimension.
These are not mutually exclusive: an Aliens Trick's unconstrained inner DP is itself often accelerated with the Convex Hull Trick or a D&C/Knuth optimization from Part 1. When none of the structural assumptions hold -- the cost function isn't convex, isn't Monge, or the count-vs-cost curve isn't convex -- fall back to the direct $O(n^2)$ or $O(n^2 k)$ DP, or look for a different structural property entirely.
10. Exercises and Mastery
Easy
- By hand, trace the lower envelope construction (insertions and any pops) for lines added in this decreasing-slope order: $y=5x$, $y=2x+4$, $y=-1x+9$, $y=-4x+16$. Which line, if any, gets popped?
Medium
- Take a DP whose transitions are lines but whose insertion order is not sorted by slope (for example, slopes derived from an unsorted input array) and whose queries are also unordered. Adapt the Li Chao Tree implementation above to answer a mixed sequence of insertions and queries, and confirm it matches a brute-force scan over all inserted lines at each query.
Hard
- Sketch (code optional) how the Aliens Trick applies to "minimum cost to paint a fence of $n$ boards using exactly $k$ distinct colors, where using color $c$ on consecutive boards is free but switching colors costs a fixed amount." Define the unconstrained inner problem (any number of color-switches allowed), describe the penalty term you would add per switch, and explain what binary search bounds on $\lambda$ would be reasonable. Then describe, in your own words, how the exact-count recovery subtlety from this lesson would apply if two different numbers of switches tied in penalized cost.
Review rhythm: tomorrow, re-derive why lines added in decreasing slope order can only be popped from the back of the envelope, without notes. Next week, implement the Li Chao Tree from scratch against a randomized brute-force checker. Several weeks later, take an unfamiliar "exactly $k$" problem and determine, from first principles, whether its cost-vs-$k$ curve is convex enough for the Aliens Trick to apply.
11. Summary Cheat Sheet
- If a transition is $dp[i]=\min_j(dp[j]+b[j]\cdot a[i])$, it's a line evaluated at a point -- reach for the Convex Hull Trick (monotone order) or a Li Chao Tree (arbitrary order).
- A Monge matrix satisfies $\text{cost}(a,c)+\text{cost}(b,d)\le\text{cost}(a,d)+\text{cost}(b,c)$ and is automatically totally monotone, which SMAWK exploits to get every row's minimum in $O(n+m)$.
- SMAWK's reduce step discards columns that can never win; its interpolate step uses odd rows' answers to bound even rows' search windows.
- The Aliens Trick turns "exactly $k$ operations" into a binary search over a per-operation penalty $\lambda$, avoiding an extra DP dimension for the count.
- Exact-$k$ recovery from the Aliens Trick requires a consistent tie-break rule (e.g., prefer more operations on ties) -- without it, a tied boundary $\lambda$ can silently recover the wrong count.
- None of these three techniques require Part 1's monotonicity argument -- they exploit convexity, the Monge property, and a tunable penalty, respectively.