DP Optimizations
You have written a dynamic program. It is correct: it agrees with brute force on every small test. It is also too slow. The table has cells and each cell takes a minimum over earlier cells, so the whole thing is , and is . Or the table is and each cell scans options, so it is , and that is steps.
This lesson is about the next move. You do not throw the DP away. You keep the same states and the same recurrence, and you look hard at the shape of the transition — the formula that says how one cell is computed from earlier ones. Certain shapes have hidden structure: the options form a sliding window, or each option is a straight line, or the best option only ever moves to the right. Spot the shape, check one condition, and a known technique removes a factor of (or turns it into ).
We will build eight tools, from the everyday to the exotic: prefix sums, the monotonic queue, the convex hull trick, the Li Chao tree, divide-and-conquer optimisation, Knuth's optimisation, the Aliens trick, and bitsets. For each one you get: when it applies, the condition you must verify, a worked example checked against the naive DP, and for the three with the trickiest code (convex hull trick, Li Chao tree, divide and conquer), a full implementation in four languages tested on hundreds of random inputs.
This lesson assumes DP Foundations (states, transitions, tabulation), and it helps to have seen Interval DP and Partition DP, because those produce most of the slow recurrences we will speed up. The monotonic deque, prefix sums, binary search and segment trees all reappear as building blocks.
Why this exists
A DP's running time is (number of states) × (work per transition). Designing the states is the creative part; you learn it in every other lesson of this module. But many natural formulations end up with a transition that is a minimum (or maximum, or sum) over a range of earlier states, and that range has length . The result is a quadratic or cubic algorithm whose state space is already as small as it can be.
Two observations made speed-ups possible:
- The options are not arbitrary numbers. They are built from the earlier DP values in a structured way. Sometimes the structure is simple (a contiguous window), sometimes geometric (each option is a line, and the minimum of lines is a convex shape), sometimes algebraic (the cost function obeys an inequality that forces the best choice to move monotonically).
- Structure can be exploited without changing the answer. Every technique here returns exactly the same table as the naive DP. That is why the standard workflow is: write the naive DP, then the optimised one, and compare them on random inputs. Every code block in this lesson does precisely that.
Historically, the inequality-based speed-ups came first. Donald Knuth showed in 1971 that the optimal binary search tree DP, naturally , runs in because the best root moves monotonically (Knuth, "Optimum binary search trees", Acta Informatica 1, 1971). F. Frances Yao generalised this in 1980 to any interval DP whose cost satisfies the quadrangle inequality (Yao, "Efficient dynamic programming using quadrangle inequalities", STOC 1980). Aggarwal, Klawe, Moran, Shor and Wilber's SMAWK algorithm (1987) and the "totally monotone matrix" theory grew from the same root. The convex hull trick, Li Chao trees and the Aliens trick were popularised much later by the competitive programming community, where tight time limits make a factor of the difference between accepted and rejected.
Pattern triggers
The trigger is never the problem statement directly. It is the recurrence you wrote. Write it in the form and look at what is inside.
| If your recurrence has… | Think of… |
|---|---|
A sum of dp[j] over a contiguous range of j | Prefix sums / a running window sum: per state |
A min/max of dp[j] + f(j) over a sliding window j ∈ [i-k, i-1] | Monotonic queue: amortised per state |
A min/max of dp[j] + a(j)·b(i) (a product of a j-part and an i-part) | Convex hull trick: each j is a line, each i is a query point |
| … with slopes added in sorted order and queries in sorted order | CHT with a monotone deque, total |
| … with slopes or queries in arbitrary order | Li Chao tree ( per op) or a dynamic hull |
Layers: dp[g][i] = min_j dp[g-1][j] + cost(j, i), cost "convex-ish" | Divide-and-conquer optimisation, |
Interval DP: dp[i][j] = min_{i≤m<j} dp[i][m] + dp[m+1][j] + w(i, j) | Knuth's optimisation, |
"Use exactly / at most k of something", and the answer is concave/convex in k | Aliens trick (WQS binary search): drop the k dimension, binary-search a penalty |
| A boolean DP where each item shifts the whole reachable set | Bitset: process 64 states per machine word |
| "Partition into k groups minimising sum of squares / variance / cost of segment" | D&C or Knuth (check the quadrangle inequality), or Aliens if is huge |
Squared distances, (x_i - x_j)^2, (S_i - S_j)^2 inside a min | Expand the square: the cross term -2·x_j·x_i is a line → CHT |
The one-line test
Fix . Look at the expression inside the min as a function of alone. If it can be written as "a value stored for " + "a value computed from ", you need only a window structure. If it is "a value for " + "a number for " × "a number for ", you need lines. If neither works, look for monotonicity of the best .
Intuition & first principles
Recognising transition shapes
Let us name the parts. A state is a cell of the DP table, like dp[i]. A transition is the rule that computes it from earlier cells. In the problems here, the rule has the form
where is the set of allowed predecessors of (often ) and is the price of jumping from to . The naive algorithm evaluates every for every : evaluations. When , that is .
Here are the shapes, from easiest to hardest, using one family of examples. Picture a frog hopping along stones ; dp[i] is the cheapest way to reach stone .
| Cost of a hop | Shape | Tool |
|---|---|---|
| (depends on only), hop length | min of dp[j] over a window | Monotonic queue |
dp[j] + h_j^2 → a line in | Convex hull trick | |
| , and we must use exactly hops | layered, cost obeys the quadrangle inequality | D&C optimisation, or Aliens |
| "number of ways" instead of "cheapest" | sum over a window | Prefix sums |
The skill is algebra: separate the variables. Anything that depends only on comes out of the min. Anything that depends only on can be stored with . What remains — the part that mixes and — decides the tool.
A tiny example: why "lines" appear
Take the frog with heights and an extra cost per hop, and cost . Expand the square:
Each earlier stone contributes a line with slope and intercept . To compute we evaluate all those lines at and take the lowest. "Lowest line at a given " is a geometry question with a fast answer: the lowest points of a set of lines form a convex, piecewise-linear curve (the lower envelope), and most lines never appear on it at all.
The four questions for every speed-up
- What exactly is inside the min? Write it with and separated.
- What condition does the technique need? Sliding window? Sorted slopes? Quadrangle inequality? Concavity in ?
- Can I prove or at least test the condition? Prove it on paper when you can. Otherwise, compute
opt(the best ) with the naive DP on random inputs and check the property the technique relies on. - Does the optimised DP match the naive DP on random inputs? Always. It is cheap and it catches nearly every bug.
flowchart TD
START["Recurrence: dp[i] = min over j of dp[j] + cost(j, i)"] --> SUM{"Sum, not min?"}
SUM -->|"yes, contiguous j"| PS["Prefix sums"]
SUM -->|"no"| WIN{"cost depends on i only, j in a sliding window?"}
WIN -->|"yes"| MQ["Monotonic queue"]
WIN -->|"no"| PROD{"cost = a(j) times b(i) plus separable terms?"}
PROD -->|"yes"| SORTED{"Slopes and queries both sorted?"}
SORTED -->|"yes"| CHT["CHT with deque, O(n)"]
SORTED -->|"no"| LC["Li Chao tree, O(n log C)"]
PROD -->|"no"| QI{"cost satisfies the quadrangle inequality?"}
QI -->|"layered dp[g][i]"| DC["Divide and conquer, O(kn log n)"]
QI -->|"interval dp[i][j]"| KN["Knuth, O(n^2)"]
QI -->|"not sure"| TEST["Test opt monotonicity on random inputs"]
START --> K{"Constraint: exactly k pieces, answer concave in k?"}
K -->|"yes"| AL["Aliens trick: penalty lambda, binary search"]
Mechanics
1. Prefix sums and sliding sums
When it applies. The transition is a sum of earlier states over a contiguous range: . This is the shape of almost every "number of ways" DP where a step can have any length from a range.
The condition. The range must be contiguous in the order you store the states. Nothing else.
The idea. Keep a prefix-sum array of the states computed so far, . Then any window sum is : two lookups instead of a loop. This is exactly the trick from Prefix Sums, applied to an array you are still filling.
Example: dice rolls (LeetCode 1155). Roll dice with faces ; in how many ways do they total target? Let ways[r][t] be the number of ways dice make total . The last die shows some face , so
The naive loop costs . With prefix sums of the previous row it is . For , , target both give 6 (the pairs 1+6, 2+5, …, 6+1). For , , target , both give modulo , but the naive one does 30 times more work.
# Sliding-sum optimisation: LeetCode 1155 "Number of Dice Rolls With Target Sum".
# ways[r][t] = sum over face f in 1..k of ways[r-1][t-f] -> a window of k cells.
MOD = 10**9 + 7
def dice_naive(n, k, target): # O(n * target * k)
ways = [1] + [0] * target
for _ in range(n):
nxt = [0] * (target + 1)
for t in range(1, target + 1):
for f in range(1, min(k, t) + 1):
nxt[t] = (nxt[t] + ways[t - f]) % MOD
ways = nxt
return ways[target]
def dice_prefix(n, k, target): # O(n * target)
ways = [1] + [0] * target
for _ in range(n):
pre = [0] * (target + 2) # pre[t+1] = ways[0] + ... + ways[t]
for t in range(target + 1):
pre[t + 1] = (pre[t] + ways[t]) % MOD
# window ways[t-k .. t-1] = pre[t] - pre[max(0, t-k)]
ways = [0] + [(pre[t] - pre[max(0, t - k)]) % MOD for t in range(1, target + 1)]
return ways[target]
assert dice_naive(2, 6, 7) == dice_prefix(2, 6, 7) == 6
assert dice_naive(30, 30, 500) == dice_prefix(30, 30, 500) == 222616187
for n in range(1, 6):
for k in range(1, 7):
for target in range(0, 31):
assert dice_naive(n, k, target) == dice_prefix(n, k, target)
print("prefix ok", dice_prefix(30, 30, 500))
Modular subtraction
pre[t] - pre[t-k] can be negative when the prefix sums are reduced modulo . In Python % fixes it; in Java, C++ and TypeScript write ((a - b) % p + p) % p.
The same trick appears as a running window sum when the window slides by one each time: add the entering element, subtract the leaving one. LeetCode 837 "New 21 Game" uses exactly that with probabilities.
2. Monotonic queue optimisation (bounded windows)
When it applies. : a min (or max) of a quantity that depends only on , over a window whose both ends move right as grows.
The condition. (1) The quantity inside depends on only, not on — so you can compare two candidates once and for all. (2) Both window ends are non-decreasing in .
The idea. This is the sliding window maximum problem from Monotonic Stack & Deque, run on the DP array as it is being filled. Keep a deque of candidate indices whose values are strictly decreasing from front to back (for a max). A candidate that is older than another candidate and no better can never be chosen again: stays in the window at least as long as does. Throw it away. The front of the deque is always the best index in the window.
Example: Constrained Subsequence Sum (LeetCode 1425). Pick a non-empty subsequence of nums so that consecutive picked indices are at most apart; maximise the sum. Let best[i] be the best sum of such a subsequence that ends at index . The previous pick is in , or there is none:
The quantity inside is best[j], which depends on only. The window slides. Monotonic queue: .
Trace on nums = [10, -2, -10, -5, 20], . The deque holds indices; the last column shows their best values, which are strictly decreasing.
| nums[i] | deque before | expired from front | max(0, best[front]) | best[i] | popped from back | deque after | best values | |
|---|---|---|---|---|---|---|---|---|
| 0 | 10 | [] | — | 0 | 10 | — | [0] | [10] |
| 1 | −2 | [0] | — | 10 | 8 | — | [0, 1] | [10, 8] |
| 2 | −10 | [0, 1] | — | 10 | 0 | — | [0, 1, 2] | [10, 8, 0] |
| 3 | −5 | [0, 1, 2] | 0 (since ) | 8 | 3 | 2 | [1, 3] | [8, 3] |
| 4 | 20 | [1, 3] | 1 (since ) | 3 | 23 | 3 | [4] | [23] |
The answer is : pick . Notice index 2 (value 0) was popped at because index 3 is newer and better (3 > 0).
# Monotonic-queue optimisation: LeetCode 1425 "Constrained Subsequence Sum".
# best[i] = nums[i] + max(0, max of best[i-k .. i-1]) -> a sliding-window maximum.
from collections import deque
import random
def constrained_naive(nums, k): # O(n * k)
best = []
for i, v in enumerate(nums):
window = best[max(0, i - k):i]
best.append(v + max(0, max(window, default=0)))
return max(best)
def constrained_deque(nums, k): # O(n)
best = [0] * len(nums)
dq = deque() # indices; best[] values strictly decreasing front to back
for i, v in enumerate(nums):
if dq and dq[0] < i - k: # front fell out of the window
dq.popleft()
best[i] = v + max(0, best[dq[0]] if dq else 0)
while dq and best[dq[-1]] <= best[i]:
dq.pop() # dominated: older and no better
dq.append(i)
return max(best)
assert constrained_deque([10, 2, -10, 5, 20], 2) == 37
assert constrained_deque([-1, -2, -3], 1) == -1
assert constrained_deque([10, -2, -10, -5, 20], 2) == 23
rng = random.Random(1425)
for _ in range(2000):
n = rng.randint(1, 30)
nums = [rng.randint(-20, 20) for _ in range(n)]
k = rng.randint(1, n)
assert constrained_deque(nums, k) == constrained_naive(nums, k)
print("monoq ok")
Why the window must be "j-only"
If the inside were , then whether beats would depend on , and you could not discard a candidate forever. That is the signal to move up to the convex hull trick.
3. The convex hull trick (CHT)
When it applies.
where and are known once is known, and is known when you start computing . Each is the line ; each is a query: "which line is lowest at ?"
The condition for the deque version. Lines are added in order of strictly decreasing slope (for a min; increasing for a max), and queries come in non-decreasing . If slopes are sorted but queries are not, keep the hull but answer each query by binary search (). If slopes are not sorted, use a Li Chao tree (next section).
Geometric intuition
Draw all the lines. For each , the minimum is the lowest line above that . Trace the lowest line from left to right and you get the lower envelope: a chain of line segments that bends upward at each corner, like the bottom of a bowl drawn with a ruler. Two facts make it fast:
- Order. As you move right along the envelope, the slopes go down. (Far to the left, where is very negative, the line with the biggest slope is lowest; far to the right, the smallest slope wins.) So if lines arrive with decreasing slopes, each new line belongs at the right end of the envelope.
- Useless lines. A line that is never the lowest anywhere can be deleted forever. With three lines of slopes , the middle one is useless exactly when takes over from before would: .
The crossing point of and is . Both denominators are positive, so cross-multiply to stay in integers:
flowchart LR
NEW["New line, smallest slope so far"] --> BACK{"Back two lines plus new: is the last one useless?"}
BACK -->|"yes"| POPB["Pop back"] --> BACK
BACK -->|"no"| PUSH["Push new line at back"]
Q["Query x, non-decreasing"] --> FRONT{"Second line lower than first at x?"}
FRONT -->|"yes"| POPF["Pop front"] --> FRONT
FRONT -->|"no"| ANS["Answer: first line at x"]
Because queries only move right, a line that loses at the front at some loses for every later too; pop it. Every line is pushed once and popped at most once, so the whole DP is after any sorting.
Worked example (AtCoder DP Z, "Frog 3")
Stones have strictly increasing heights , hopping from to costs with , and the frog starts on stone 0. As derived above, stone becomes the line , , queried at ; then . Heights increase, so slopes decrease and queries increase: the deque version applies. Write for stone 's line.
| deque before (stones) | popped from front | best | new line | popped from back | deque after | |||
|---|---|---|---|---|---|---|---|---|
| 0 | — | — | — | — | 0 | — | [0] | |
| 1 | 2 | [0] | — | 0 | — | [0, 1] | ||
| 2 | 3 | [0, 1] | — | 0 | 1 | [0, 2] | ||
| 3 | 4 | [0, 2] | — | 0 | — | [0, 2, 3] | ||
| 4 | 6 | [0, 2, 3] | 0, 2 | 3 | — | [3, 4] |
The answer is . The naive DP gives too.
Two moments are worth slowing down for:
- , back pop. The deque holds and ; the new line is . and cross at . and cross at . So takes over from before ever could: is never the lowest line, and it goes. Integer test: . True, pop.
- , front pops. At : , , . beats (pop ); ties (pop — ties may go either way). The min is , and indeed stones 2 and 3 both give .
Implementation: CHT with a monotone deque
Each program runs the worked example, the AtCoder sample (, , answer 20), and 500 random instances against the DP.
# Convex hull trick with a monotone deque.
# Problem (AtCoder DP Z "Frog 3"): heights h[0] < h[1] < ... < h[n-1].
# dp[0] = 0, dp[i] = min over j < i of dp[j] + (h[i] - h[j])^2 + C.
# Expand: dp[i] = h[i]^2 + C + min_j ( -2*h[j] * h[i] + dp[j] + h[j]^2 )
# -> line j has slope m = -2*h[j] and intercept b = dp[j] + h[j]^2,
# evaluated at x = h[i]. Slopes decrease, queries increase.
from collections import deque
def useless(l1, l2, l3):
"""l2 never strictly below both l1 and l3. Slopes m1 > m2 > m3."""
(m1, b1), (m2, b2), (m3, b3) = l1, l2, l3
# intersect(l1, l3) <= intersect(l1, l2), cross-multiplied (denominators > 0)
return (b3 - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m3)
def frog3_cht(h, c):
n = len(h)
dp = [0] * n
hull = deque([(-2 * h[0], dp[0] + h[0] * h[0])])
for i in range(1, n):
x = h[i]
# Queries increase: drop front lines that are no longer the best.
while len(hull) >= 2 and hull[1][0] * x + hull[1][1] <= hull[0][0] * x + hull[0][1]:
hull.popleft()
m, b = hull[0]
dp[i] = m * x + b + x * x + c
new = (-2 * h[i], dp[i] + h[i] * h[i])
# Slopes decrease: add at the back, removing lines the new one makes useless.
while len(hull) >= 2 and useless(hull[-2], hull[-1], new):
hull.pop()
hull.append(new)
return dp[-1]
def frog3_naive(h, c):
n = len(h)
dp = [0] + [float("inf")] * (n - 1)
for i in range(1, n):
dp[i] = min(dp[j] + (h[i] - h[j]) ** 2 + c for j in range(i))
return dp[-1]
class ParkMiller:
def __init__(self, seed):
self.s = seed
def next(self, bound):
self.s = self.s * 48271 % 2147483647
return self.s % bound
def main():
assert frog3_cht([1, 2, 3, 4, 5], 6) == 20 # AtCoder sample
assert frog3_cht([1, 2, 3, 4, 6], 5) == 23 # the worked example in the trace table
assert frog3_cht([1, 3, 4, 7, 8, 10], 5) == frog3_naive([1, 3, 4, 7, 8, 10], 5)
rng = ParkMiller(2024)
for _ in range(500):
n = 1 + rng.next(40)
h, cur = [], 0
for _ in range(n):
cur += 1 + rng.next(30)
h.append(cur)
c = rng.next(1000)
assert frog3_cht(h, c) == frog3_naive(h, c)
print("cht ok", frog3_cht([1, 3, 4, 7, 8, 10], 5))
main()
import java.util.Arrays;
public class Main {
// Convex hull trick with a monotone deque (AtCoder DP Z "Frog 3").
// Line j: slope -2*h[j], intercept dp[j] + h[j]^2, queried at x = h[i].
// Slopes strictly decrease and queries increase, so a deque suffices.
static boolean useless(long m1, long b1, long m2, long b2, long m3, long b3) {
// intersect(l1, l3) <= intersect(l1, l2), cross-multiplied.
// Products can reach ~1e18 for h ~ 1e6: switch to Math.multiplyHigh or BigInteger beyond that.
return (b3 - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m3);
}
static long frog3Cht(long[] h, long c) {
int n = h.length;
long[] dp = new long[n];
long[] ms = new long[n], bs = new long[n];
int head = 0, tail = 0; // deque is ms/bs[head..tail)
ms[tail] = -2 * h[0]; bs[tail] = h[0] * h[0]; tail++;
for (int i = 1; i < n; i++) {
long x = h[i];
while (tail - head >= 2 && ms[head + 1] * x + bs[head + 1] <= ms[head] * x + bs[head]) head++;
dp[i] = ms[head] * x + bs[head] + x * x + c;
long m = -2 * h[i], b = dp[i] + h[i] * h[i];
while (tail - head >= 2 && useless(ms[tail - 2], bs[tail - 2], ms[tail - 1], bs[tail - 1], m, b)) tail--;
ms[tail] = m; bs[tail] = b; tail++;
}
return dp[n - 1];
}
static long frog3Naive(long[] h, long c) {
int n = h.length;
long[] dp = new long[n];
Arrays.fill(dp, Long.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
dp[i] = Math.min(dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + c);
return dp[n - 1];
}
static long seed = 2024;
static int next(int bound) {
seed = seed * 48271 % 2147483647L;
return (int) (seed % bound);
}
public static void main(String[] args) {
if (frog3Cht(new long[]{1, 2, 3, 4, 5}, 6) != 20) throw new AssertionError();
if (frog3Cht(new long[]{1, 2, 3, 4, 6}, 5) != 23) throw new AssertionError();
long[] ex = {1, 3, 4, 7, 8, 10};
if (frog3Cht(ex, 5) != 42 || frog3Naive(ex, 5) != 42) throw new AssertionError();
for (int t = 0; t < 500; t++) {
int n = 1 + next(40);
long[] h = new long[n];
long cur = 0;
for (int i = 0; i < n; i++) { cur += 1 + next(30); h[i] = cur; }
long c = next(1000);
if (frog3Cht(h, c) != frog3Naive(h, c)) throw new AssertionError("mismatch");
}
System.out.println("cht ok " + frog3Cht(ex, 5));
}
}
#include <cassert>
#include <climits>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
// Convex hull trick with a monotone deque (AtCoder DP Z "Frog 3").
// Line j: slope -2*h[j], intercept dp[j] + h[j]^2, queried at x = h[i].
struct Line {
ll m, b;
ll at(ll x) const { return m * x + b; }
};
// l2 is useless if intersect(l1, l3) <= intersect(l1, l2). Slopes m1 > m2 > m3.
// __int128 keeps the cross products exact even when they exceed 64 bits.
bool useless(const Line& l1, const Line& l2, const Line& l3) {
return (__int128)(l3.b - l1.b) * (l1.m - l2.m) <= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}
ll frog3Cht(const vector<ll>& h, ll c) {
size_t n = h.size();
vector<ll> dp(n, 0);
vector<Line> hull; // hull[head..] is the deque
size_t head = 0;
hull.push_back({-2 * h[0], h[0] * h[0]});
for (size_t i = 1; i < n; i++) {
ll x = h[i];
while (hull.size() - head >= 2 && hull[head + 1].at(x) <= hull[head].at(x)) head++;
dp[i] = hull[head].at(x) + x * x + c;
Line nl{-2 * h[i], dp[i] + h[i] * h[i]};
while (hull.size() - head >= 2 && useless(hull[hull.size() - 2], hull.back(), nl)) hull.pop_back();
hull.push_back(nl);
}
return dp[n - 1];
}
ll frog3Naive(const vector<ll>& h, ll c) {
size_t n = h.size();
vector<ll> dp(n, LLONG_MAX);
dp[0] = 0;
for (size_t i = 1; i < n; i++)
for (size_t j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + c);
return dp[n - 1];
}
uint64_t seed = 2024;
int nextInt(int bound) {
seed = seed * 48271 % 2147483647ULL;
return (int)(seed % bound);
}
int main() {
assert(frog3Cht({1, 2, 3, 4, 5}, 6) == 20);
assert(frog3Cht({1, 2, 3, 4, 6}, 5) == 23);
vector<ll> ex{1, 3, 4, 7, 8, 10};
assert(frog3Cht(ex, 5) == 42 && frog3Naive(ex, 5) == 42);
for (int t = 0; t < 500; t++) {
int n = 1 + nextInt(40);
vector<ll> h(n);
ll cur = 0;
for (int i = 0; i < n; i++) { cur += 1 + nextInt(30); h[i] = cur; }
ll c = nextInt(1000);
assert(frog3Cht(h, c) == frog3Naive(h, c));
}
cout << "cht ok " << frog3Cht(ex, 5) << "\n";
}
// Convex hull trick with a monotone deque (AtCoder DP Z "Frog 3").
// Line j: slope -2*h[j], intercept dp[j] + h[j]^2, queried at x = h[i].
// Plain numbers are exact up to 2^53; use BigInt if products can exceed that.
type Line = { m: number; b: number };
const at = (l: Line, x: number): number => l.m * x + l.b;
function useless(l1: Line, l2: Line, l3: Line): boolean {
// intersect(l1, l3) <= intersect(l1, l2); slopes m1 > m2 > m3.
return (l3.b - l1.b) * (l1.m - l2.m) <= (l2.b - l1.b) * (l1.m - l3.m);
}
function frog3Cht(h: number[], c: number): number {
const n = h.length;
const dp = new Array<number>(n).fill(0);
const hull: Line[] = [{ m: -2 * h[0], b: h[0] * h[0] }];
let head = 0; // hull[head..] is the deque
for (let i = 1; i < n; i++) {
const x = h[i];
while (hull.length - head >= 2 && at(hull[head + 1], x) <= at(hull[head], x)) head++;
dp[i] = at(hull[head], x) + x * x + c;
const nl: Line = { m: -2 * h[i], b: dp[i] + h[i] * h[i] };
while (hull.length - head >= 2 && useless(hull[hull.length - 2], hull[hull.length - 1], nl)) hull.pop();
hull.push(nl);
}
return dp[n - 1];
}
function frog3Naive(h: number[], c: number): number {
const n = h.length;
const dp = new Array<number>(n).fill(Infinity);
dp[0] = 0;
for (let i = 1; i < n; i++)
for (let j = 0; j < i; j++) dp[i] = Math.min(dp[i], dp[j] + (h[i] - h[j]) ** 2 + c);
return dp[n - 1];
}
let seed = 2024;
function nextInt(bound: number): number {
seed = (seed * 48271) % 2147483647;
return seed % bound;
}
function assert(cond: boolean, msg = "assertion failed"): void {
if (!cond) throw new Error(msg);
}
assert(frog3Cht([1, 2, 3, 4, 5], 6) === 20);
assert(frog3Cht([1, 2, 3, 4, 6], 5) === 23);
const ex = [1, 3, 4, 7, 8, 10];
assert(frog3Cht(ex, 5) === 42 && frog3Naive(ex, 5) === 42);
for (let t = 0; t < 500; t++) {
const n = 1 + nextInt(40);
const h: number[] = [];
let cur = 0;
for (let i = 0; i < n; i++) { cur += 1 + nextInt(30); h.push(cur); }
const c = nextInt(1000);
assert(frog3Cht(h, c) === frog3Naive(h, c), "mismatch");
}
console.log("cht ok " + frog3Cht(ex, 5));
Overflow in the "useless" test
The cross-multiplied test multiplies an intercept by a slope difference. With Frog 3's limits (heights up to , up to ), every is at most one direct hop from stone 0, about , so intercepts stay below about while slope differences reach . Products reach about — uncomfortably close to the signed 64-bit limit of , and over it for slightly larger inputs. The C++ version uses __int128. In Java use Math.multiplyHigh or compare as double with care; in TypeScript use BigInt for large inputs. Alternatively compare crossing points as long double, accepting a tiny risk on near-ties.
Max instead of min, increasing instead of decreasing
All four combinations reduce to the one above. To maximise, negate both slope and intercept, minimise, negate the answer. If slopes arrive increasing for a min, the new line belongs at the left end of the envelope; the simplest fix is to substitute (negate slopes and query points), which reverses both orders.
4. The Li Chao tree
When it applies. Same shape as CHT — a min of lines at a query point — but lines arrive with arbitrary slopes and queries come at arbitrary , interleaved. Example: CSES "Monster Game II", where and neither the skill factors (slopes) nor the monster strengths (query points) are sorted.
The condition. Queries are at integer points (or points from a known finite set) in a range , and any two lines cross at most once — true for straight lines, and also for any family of functions in which two members cross at most once, such as parabolas with equal leading coefficients.
The idea. Build a segment tree over the -range (see Segment Trees). Each node stores one line: the one that is lowest at the node's midpoint among the lines that reached that node. When inserting a new line into a node with interval and midpoint :
- Compare the new line and the stored line at . The winner stays in the node.
- The loser can still be lowest somewhere — but only on one side of , because two lines cross at most once. Compare them at : if the winner at differs from the winner at , the crossing is in , so push the loser into the left child; otherwise push it into the right child.
A query at walks from the root to the leaf for and takes the minimum of the lines stored on that path. Each insert and each query touches one node per level: .
flowchart TD
N1["node 1: [0,7], mid 3, keeps the winner at x=3"] --> N2["node 2: [0,3]"]
N1 --> N3["node 3: [4,7], mid 5"]
N3 --> N6["node 6: [4,5], mid 4"]
N3 --> N7["node 7: [6,7]"]
Trace on domain with three lines inserted in this order: , , .
| Insert | Node , mid | Stored before | New better at ? | New better at mid? | Node keeps | Loser goes to |
|---|---|---|---|---|---|---|
| A | 1: [0, 7], 3 | empty | yes | yes | A | — (nothing left) |
| B | 1: [0, 7], 3 | A | yes () | yes () | B | right child (A wins nowhere left of 3) |
| B | 3: [4, 7], 5 | empty | yes | yes | A | — |
| C | 1: [0, 7], 3 | B | no () | no (, tie) | B | right child |
| C | 3: [4, 7], 5 | A | yes () | no () | A | left child |
| C | 6: [4, 5], 4 | empty | yes | yes | C | — |
Query : the path is node 1 (), node 3 (), node 6 (); the answer is 3. Brute force over at : . Query : node 1 gives , and nothing lower lies below, so the answer is 1. Every in was checked against brute force.
Li Chao versus a sorted hull
Li Chao keeps lines that are never optimal (it never deletes), costs per query instead of amortised , and needs the query domain in advance. In exchange it has no order requirements, no division, no fragile "useless" test, and it extends to line segments (insert into nodes, then ) and to persistent and dynamic (pointer-based) versions for huge domains like .
Implementation: Li Chao tree
Each program tests the raw tree on 300 random sequences of interleaved inserts and queries against a brute-force minimum, then the Monster-Game-style DP on 300 random instances against the DP.
# Li Chao tree: insert lines y = m*x + b in any order, query min at any integer x in [lo, hi].
# Each node keeps the line that wins at its midpoint; the loser can only win on one side.
INF = float("inf")
class LiChao:
def __init__(self, lo, hi):
self.lo, self.hi = lo, hi
size = 4 * (hi - lo + 1)
self.m = [0] * size
self.b = [INF] * size # "no line yet": evaluates to +inf everywhere
def insert(self, m, b):
node, l, r = 1, self.lo, self.hi
while True:
mid = (l + r) // 2
left_better = m * l + b < self.m[node] * l + self.b[node]
mid_better = m * mid + b < self.m[node] * mid + self.b[node]
if mid_better: # keep the midpoint winner in this node
self.m[node], m = m, self.m[node]
self.b[node], b = b, self.b[node]
if l == r:
return
if left_better != mid_better: # loser still wins somewhere in [l, mid]
node, r = 2 * node, mid
else: # ... or somewhere in [mid + 1, r]
node, l = 2 * node + 1, mid + 1
def query(self, x):
node, l, r, best = 1, self.lo, self.hi, INF
while True:
best = min(best, self.m[node] * x + self.b[node])
if l == r:
return best
mid = (l + r) // 2
if x <= mid:
node, r = 2 * node, mid
else:
node, l = 2 * node + 1, mid + 1
def monster_game_lichao(start_skill, s, f, max_f):
"""dp[i] = min(start*f[i], min_{j<i} dp[j] + s[j]*f[i]); slopes and queries in any order."""
tree = LiChao(1, max_f)
tree.insert(start_skill, 0)
dp = 0
for si, fi in zip(s, f):
dp = tree.query(fi)
tree.insert(si, dp)
return dp
def monster_game_naive(start_skill, s, f):
lines = [(start_skill, 0)]
dp = 0
for si, fi in zip(s, f):
dp = min(m * fi + b for m, b in lines)
lines.append((si, dp))
return dp
class ParkMiller:
def __init__(self, seed):
self.s = seed
def next(self, bound):
self.s = self.s * 48271 % 2147483647
return self.s % bound
def main():
assert monster_game_lichao(2, [3, 1, 4, 2], [5, 9, 2, 6], 10) == monster_game_naive(2, [3, 1, 4, 2], [5, 9, 2, 6])
rng = ParkMiller(7)
for _ in range(300): # raw tree vs brute force, interleaved operations
tree, lines = LiChao(0, 1000), []
for _ in range(60):
if rng.next(2) == 0 or not lines:
m, b = rng.next(201) - 100, rng.next(20001) - 10000
tree.insert(m, b)
lines.append((m, b))
else:
x = rng.next(1001)
assert tree.query(x) == min(m * x + b for m, b in lines)
for _ in range(300): # the DP vs the O(n^2) DP
n = 1 + rng.next(50)
s = [1 + rng.next(1000) for _ in range(n)]
f = [1 + rng.next(1000) for _ in range(n)]
x = 1 + rng.next(1000)
assert monster_game_lichao(x, s, f, 1000) == monster_game_naive(x, s, f)
print("lichao ok", monster_game_lichao(2, [3, 1, 4, 2], [5, 9, 2, 6], 10))
main()
import java.util.ArrayList;
import java.util.List;
public class Main {
// Li Chao tree over integer x in [lo, hi]: insert lines in any order, query the minimum at x.
static final long INF = Long.MAX_VALUE / 4;
static final class LiChao {
final int lo, hi;
final long[] m, b;
LiChao(int lo, int hi) {
this.lo = lo; this.hi = hi;
int size = 4 * (hi - lo + 1);
m = new long[size];
b = new long[size];
java.util.Arrays.fill(b, INF); // empty node: the line y = INF
}
private long eval(int node, long x) { return b[node] == INF ? INF : m[node] * x + b[node]; }
void insert(long nm, long nb) {
int node = 1, l = lo, r = hi;
while (true) {
int mid = (l + r) >> 1;
boolean leftBetter = nm * l + nb < eval(node, l);
boolean midBetter = nm * mid + nb < eval(node, mid);
if (midBetter) { // node keeps the midpoint winner
long t = m[node]; m[node] = nm; nm = t;
t = b[node]; b[node] = nb; nb = t;
}
if (l == r || nb == INF) return; // nothing left to push down
if (leftBetter != midBetter) { node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
long query(long x) {
int node = 1, l = lo, r = hi;
long best = INF;
while (true) {
best = Math.min(best, eval(node, x));
if (l == r) return best;
int mid = (l + r) >> 1;
if (x <= mid) { node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
}
// dp[i] = min(start*f[i], min_{j<i} dp[j] + s[j]*f[i]): slopes and queries in any order.
static long monsterGameLiChao(long start, long[] s, long[] f, int maxF) {
LiChao tree = new LiChao(1, maxF);
tree.insert(start, 0);
long dp = 0;
for (int i = 0; i < s.length; i++) {
dp = tree.query(f[i]);
tree.insert(s[i], dp);
}
return dp;
}
static long monsterGameNaive(long start, long[] s, long[] f) {
List<long[]> lines = new ArrayList<>();
lines.add(new long[]{start, 0});
long dp = 0;
for (int i = 0; i < s.length; i++) {
dp = INF;
for (long[] ln : lines) dp = Math.min(dp, ln[0] * f[i] + ln[1]);
lines.add(new long[]{s[i], dp});
}
return dp;
}
static long seed = 7;
static int next(int bound) {
seed = seed * 48271 % 2147483647L;
return (int) (seed % bound);
}
public static void main(String[] args) {
if (monsterGameLiChao(2, new long[]{3, 1, 4, 2}, new long[]{5, 9, 2, 6}, 10) != 12) throw new AssertionError();
for (int t = 0; t < 300; t++) {
LiChao tree = new LiChao(0, 1000);
List<long[]> lines = new ArrayList<>();
for (int op = 0; op < 60; op++) {
if (next(2) == 0 || lines.isEmpty()) {
long m = next(201) - 100, b = next(20001) - 10000;
tree.insert(m, b);
lines.add(new long[]{m, b});
} else {
long x = next(1001), best = INF;
for (long[] ln : lines) best = Math.min(best, ln[0] * x + ln[1]);
if (tree.query(x) != best) throw new AssertionError("tree mismatch");
}
}
}
for (int t = 0; t < 300; t++) {
int n = 1 + next(50);
long[] s = new long[n], f = new long[n];
for (int i = 0; i < n; i++) s[i] = 1 + next(1000);
for (int i = 0; i < n; i++) f[i] = 1 + next(1000);
long x = 1 + next(1000);
if (monsterGameLiChao(x, s, f, 1000) != monsterGameNaive(x, s, f)) throw new AssertionError("dp mismatch");
}
System.out.println("lichao ok " + monsterGameLiChao(2, new long[]{3, 1, 4, 2}, new long[]{5, 9, 2, 6}, 10));
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
// Li Chao tree over integer x in [lo, hi]: insert lines in any order, query the minimum at x.
const ll INF = LLONG_MAX / 4;
struct Line {
ll m = 0, b = INF; // default: the empty line y = INF
ll at(ll x) const { return b == INF ? INF : m * x + b; }
};
struct LiChao {
int lo, hi;
vector<Line> t;
LiChao(int lo_, int hi_) : lo(lo_), hi(hi_), t(4 * (hi_ - lo_ + 1)) {}
void insert(Line nl) {
int node = 1, l = lo, r = hi;
while (true) {
int mid = (l + r) >> 1;
bool leftBetter = nl.at(l) < t[node].at(l);
bool midBetter = nl.at(mid) < t[node].at(mid);
if (midBetter) swap(t[node], nl); // node keeps the midpoint winner
if (l == r || nl.b == INF) return;
if (leftBetter != midBetter) { node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
ll query(ll x) const {
int node = 1, l = lo, r = hi;
ll best = INF;
while (true) {
best = min(best, t[node].at(x));
if (l == r) return best;
int mid = (l + r) >> 1;
if (x <= mid) { node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
};
// dp[i] = min(start*f[i], min_{j<i} dp[j] + s[j]*f[i]): slopes and queries in any order.
ll monsterGameLiChao(ll start, const vector<ll>& s, const vector<ll>& f, int maxF) {
LiChao tree(1, maxF);
tree.insert({start, 0});
ll dp = 0;
for (size_t i = 0; i < s.size(); i++) {
dp = tree.query(f[i]);
tree.insert({s[i], dp});
}
return dp;
}
ll monsterGameNaive(ll start, const vector<ll>& s, const vector<ll>& f) {
vector<Line> lines{{start, 0}};
ll dp = 0;
for (size_t i = 0; i < s.size(); i++) {
dp = INF;
for (const Line& ln : lines) dp = min(dp, ln.at(f[i]));
lines.push_back({s[i], dp});
}
return dp;
}
uint64_t seed = 7;
int nextInt(int bound) {
seed = seed * 48271 % 2147483647ULL;
return (int)(seed % bound);
}
int main() {
assert(monsterGameLiChao(2, {3, 1, 4, 2}, {5, 9, 2, 6}, 10) == 12);
for (int t = 0; t < 300; t++) {
LiChao tree(0, 1000);
vector<Line> lines;
for (int op = 0; op < 60; op++) {
if (nextInt(2) == 0 || lines.empty()) {
ll m = nextInt(201) - 100;
ll b = nextInt(20001) - 10000;
tree.insert({m, b});
lines.push_back({m, b});
} else {
ll x = nextInt(1001), best = INF;
for (const Line& ln : lines) best = min(best, ln.at(x));
assert(tree.query(x) == best);
}
}
}
for (int t = 0; t < 300; t++) {
int n = 1 + nextInt(50);
vector<ll> s(n), f(n);
for (int i = 0; i < n; i++) s[i] = 1 + nextInt(1000);
for (int i = 0; i < n; i++) f[i] = 1 + nextInt(1000);
ll x = 1 + nextInt(1000);
assert(monsterGameLiChao(x, s, f, 1000) == monsterGameNaive(x, s, f));
}
cout << "lichao ok " << monsterGameLiChao(2, {3, 1, 4, 2}, {5, 9, 2, 6}, 10) << "\n";
}
// Li Chao tree over integer x in [lo, hi]: insert lines in any order, query the minimum at x.
class LiChao {
readonly lo: number;
readonly hi: number;
readonly m: number[];
readonly b: number[];
constructor(lo: number, hi: number) {
this.lo = lo;
this.hi = hi;
const size = 4 * (hi - lo + 1);
this.m = new Array<number>(size).fill(0);
this.b = new Array<number>(size).fill(Infinity); // empty node: y = +inf
}
insert(nm: number, nb: number): void {
let node = 1, l = this.lo, r = this.hi;
while (true) {
const mid = (l + r) >> 1;
const leftBetter = nm * l + nb < this.m[node] * l + this.b[node];
const midBetter = nm * mid + nb < this.m[node] * mid + this.b[node];
if (midBetter) { // node keeps the midpoint winner
[this.m[node], nm] = [nm, this.m[node]];
[this.b[node], nb] = [nb, this.b[node]];
}
if (l === r) return;
if (leftBetter !== midBetter) { node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
query(x: number): number {
let node = 1, l = this.lo, r = this.hi, best = Infinity;
while (true) {
best = Math.min(best, this.m[node] * x + this.b[node]);
if (l === r) return best;
const mid = (l + r) >> 1;
if (x <= mid) { node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
}
// dp[i] = min(start*f[i], min_{j<i} dp[j] + s[j]*f[i]): slopes and queries in any order.
function monsterGameLiChao(start: number, s: number[], f: number[], maxF: number): number {
const tree = new LiChao(1, maxF);
tree.insert(start, 0);
let dp = 0;
for (let i = 0; i < s.length; i++) {
dp = tree.query(f[i]);
tree.insert(s[i], dp);
}
return dp;
}
function monsterGameNaive(start: number, s: number[], f: number[]): number {
const lines: [number, number][] = [[start, 0]];
let dp = 0;
for (let i = 0; i < s.length; i++) {
dp = Math.min(...lines.map(([m, b]) => m * f[i] + b));
lines.push([s[i], dp]);
}
return dp;
}
let seed = 7;
function nextInt(bound: number): number {
seed = (seed * 48271) % 2147483647;
return seed % bound;
}
function assert(cond: boolean, msg = "assertion failed"): void {
if (!cond) throw new Error(msg);
}
assert(monsterGameLiChao(2, [3, 1, 4, 2], [5, 9, 2, 6], 10) === 12);
for (let t = 0; t < 300; t++) {
const tree = new LiChao(0, 1000);
const lines: [number, number][] = [];
for (let op = 0; op < 60; op++) {
if (nextInt(2) === 0 || lines.length === 0) {
const m = nextInt(201) - 100, b = nextInt(20001) - 10000;
tree.insert(m, b);
lines.push([m, b]);
} else {
const x = nextInt(1001);
assert(tree.query(x) === Math.min(...lines.map(([m, b]) => m * x + b)), "tree mismatch");
}
}
}
for (let t = 0; t < 300; t++) {
const n = 1 + nextInt(50);
const s: number[] = [], f: number[] = [];
for (let i = 0; i < n; i++) s.push(1 + nextInt(1000));
for (let i = 0; i < n; i++) f.push(1 + nextInt(1000));
const x = 1 + nextInt(1000);
assert(monsterGameLiChao(x, s, f, 1000) === monsterGameNaive(x, s, f), "dp mismatch");
}
console.log("lichao ok " + monsterGameLiChao(2, [3, 1, 4, 2], [5, 9, 2, 6], 10));
5. Divide-and-conquer optimisation
When it applies. A layered DP, usually "split the first items into groups":
where is the price of making items one group. Naively each layer is and there are layers: .
The condition. Let be the (smallest) that achieves the minimum for in a given layer. The technique needs
the monotonicity of the optimal split point. A sufficient condition, and the one you usually check, is that the cost satisfies the quadrangle inequality (QI):
In words: for two overlapping intervals, the "crossed" pair (each covering part) costs no more than the "nested" pair (one inside the other). Costs that grow faster than linearly with the group's content — squares of sums, within-group variance, — usually satisfy it.
The idea. Compute the layer's middle entry, , by brute force over its whole candidate range; call the winner . Monotonicity says every has and every has . Recurse on the two halves with those narrowed candidate ranges.
solve(lo, hi, optLo, optHi): # fill dp[lo..hi]; their opts lie in [optLo, optHi]
if lo > hi: return
mid = (lo + hi) / 2
scan j in [optLo, min(mid-1, optHi)], keep the best -> dp[mid], bestJ
solve(lo, mid-1, optLo, bestJ)
solve(mid+1, hi, bestJ, optHi)
flowchart TD
R["solve i in 1..8, j in 0..7: scan at mid 4"] --> L["solve i in 1..3, j in 0..opt(4)"]
R --> RR["solve i in 5..8, j in opt(4)..7"]
L --> L1["i = 1"]
L --> L2["i = 3"]
RR --> R1["i = 5"]
RR --> R2["i = 7, 8"]
Why per layer. The recursion has levels. On any one level the candidate ranges of the calls overlap only at their endpoints, so together they cover about + (number of calls) indices. That is work per level and per layer, in total.
Worked example
Split into exactly non-empty contiguous groups, minimising the sum of (group sum). With prefix sums , . Here is the whole table the naive DP computes, with below each value (the smallest best ):
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| 9 | 16 | 64 | 81 | 196 | 529 | 625 | 961 | |
| — | 10 | 32 | 41 | 100 | 277 | 317 | 485 | |
| — | 1 | 2 | 2 | 3 | 4 | 5 | 5 | |
| — | — | 26 | 33 | 66 | 181 | 221 | 341 | |
| — | — | 2 | 3 | 4 | 5 | 5 | 6 |
The rows never decrease — exactly what the technique needs. The answer is : groups , , with sums and . (Notice the optimum does not make the three sums equal: is impossible with these numbers.)
How much work is saved? Counting cost evaluations on random arrays: for , , the naive DP does and divide and conquer does (52× fewer). For , : versus (172× fewer). The ratio grows like .
Checking the condition for this cost
Let (prefix sums of non-negative numbers never decrease). Then
which is the quadrangle inequality: nested pair crossed pair. (Expand all four squares; the terms cancel.) With negative numbers allowed, is not monotone and the argument fails — and so can the technique.
Implementation: divide-and-conquer optimisation
Each program checks the worked example and 400 random instances (random , values , random ) against the DP.
# Divide & conquer optimisation.
# Split a[0..n) (all values >= 0) into exactly k non-empty contiguous groups and
# minimise the sum of (group sum)^2. With prefix sums S:
# dp[g][i] = min over j in [g-1, i-1] of dp[g-1][j] + (S[i] - S[j])^2
# The cost (S[i]-S[j])^2 satisfies the quadrangle inequality, so the best j
# (opt) is non-decreasing in i, and each layer costs O(n log n).
import sys
INF = float("inf")
def min_squared_partition(a, k):
n = len(a)
S = [0] * (n + 1)
for i, v in enumerate(a):
S[i + 1] = S[i] + v
def cost(j, i): # cost of the group a[j..i)
return (S[i] - S[j]) ** 2
prev = [INF] * (n + 1)
prev[0] = 0
for g in range(1, k + 1):
cur = [INF] * (n + 1)
def solve(lo, hi, opt_lo, opt_hi):
"""Fill cur[lo..hi], knowing opt for those i lies in [opt_lo, opt_hi]."""
if lo > hi:
return
mid = (lo + hi) // 2
best, best_j = INF, opt_lo
for j in range(opt_lo, min(mid - 1, opt_hi) + 1):
val = prev[j] + cost(j, mid)
if val < best:
best, best_j = val, j
cur[mid] = best
solve(lo, mid - 1, opt_lo, best_j) # left half: opt <= best_j
solve(mid + 1, hi, best_j, opt_hi) # right half: opt >= best_j
solve(g, n, g - 1, n - 1)
prev = cur
return prev[n]
def min_squared_partition_naive(a, k):
n = len(a)
S = [0] * (n + 1)
for i, v in enumerate(a):
S[i + 1] = S[i] + v
prev = [0] + [INF] * n
for g in range(1, k + 1):
cur = [INF] * (n + 1)
for i in range(g, n + 1):
for j in range(g - 1, i):
cur[i] = min(cur[i], prev[j] + (S[i] - S[j]) ** 2)
prev = cur
return prev[n]
class ParkMiller:
def __init__(self, seed):
self.s = seed
def next(self, bound):
self.s = self.s * 48271 % 2147483647
return self.s % bound
def main():
sys.setrecursionlimit(10_000)
example = [3, 1, 4, 1, 5, 9, 2, 6]
assert min_squared_partition(example, 3) == min_squared_partition_naive(example, 3)
rng = ParkMiller(99)
for _ in range(400):
n = 1 + rng.next(30)
a = [rng.next(50) for _ in range(n)]
k = 1 + rng.next(n)
assert min_squared_partition(a, k) == min_squared_partition_naive(a, k)
print("dnc ok", min_squared_partition(example, 3))
main()
import java.util.Arrays;
public class Main {
// Divide & conquer optimisation: split a (values >= 0) into exactly k non-empty
// contiguous groups, minimising the sum of (group sum)^2.
// dp[g][i] = min_{g-1 <= j < i} dp[g-1][j] + (S[i] - S[j])^2, opt monotone in i.
static final long INF = Long.MAX_VALUE / 4;
static long[] S, prev, cur;
static long cost(int j, int i) { long d = S[i] - S[j]; return d * d; }
static void solve(int lo, int hi, int optLo, int optHi) {
if (lo > hi) return;
int mid = (lo + hi) >>> 1;
long best = INF;
int bestJ = optLo;
for (int j = optLo; j <= Math.min(mid - 1, optHi); j++) {
if (prev[j] >= INF) continue;
long val = prev[j] + cost(j, mid);
if (val < best) { best = val; bestJ = j; }
}
cur[mid] = best;
solve(lo, mid - 1, optLo, bestJ);
solve(mid + 1, hi, bestJ, optHi);
}
static long minSquaredPartition(long[] a, int k) {
int n = a.length;
S = new long[n + 1];
for (int i = 0; i < n; i++) S[i + 1] = S[i] + a[i];
prev = new long[n + 1];
Arrays.fill(prev, INF);
prev[0] = 0;
for (int g = 1; g <= k; g++) {
cur = new long[n + 1];
Arrays.fill(cur, INF);
solve(g, n, g - 1, n - 1);
prev = cur;
}
return prev[n];
}
static long minSquaredPartitionNaive(long[] a, int k) {
int n = a.length;
long[] s = new long[n + 1];
for (int i = 0; i < n; i++) s[i + 1] = s[i] + a[i];
long[] p = new long[n + 1];
Arrays.fill(p, INF);
p[0] = 0;
for (int g = 1; g <= k; g++) {
long[] c = new long[n + 1];
Arrays.fill(c, INF);
for (int i = g; i <= n; i++)
for (int j = g - 1; j < i; j++)
if (p[j] < INF) c[i] = Math.min(c[i], p[j] + (s[i] - s[j]) * (s[i] - s[j]));
p = c;
}
return p[n];
}
static long seed = 99;
static int next(int bound) {
seed = seed * 48271 % 2147483647L;
return (int) (seed % bound);
}
public static void main(String[] args) {
long[] example = {3, 1, 4, 1, 5, 9, 2, 6};
if (minSquaredPartition(example, 3) != 341) throw new AssertionError();
if (minSquaredPartitionNaive(example, 3) != 341) throw new AssertionError();
for (int t = 0; t < 400; t++) {
int n = 1 + next(30);
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = next(50);
int k = 1 + next(n);
if (minSquaredPartition(a, k) != minSquaredPartitionNaive(a, k)) throw new AssertionError("mismatch");
}
System.out.println("dnc ok " + minSquaredPartition(example, 3));
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
// Divide & conquer optimisation: split a (values >= 0) into exactly k non-empty
// contiguous groups, minimising the sum of (group sum)^2.
// dp[g][i] = min_{g-1 <= j < i} dp[g-1][j] + (S[i] - S[j])^2, opt monotone in i.
const ll INF = LLONG_MAX / 4;
struct Partitioner {
vector<ll> S, prev, cur;
ll cost(int j, int i) const { ll d = S[i] - S[j]; return d * d; }
void solve(int lo, int hi, int optLo, int optHi) {
if (lo > hi) return;
int mid = (lo + hi) / 2;
ll best = INF;
int bestJ = optLo;
for (int j = optLo; j <= min(mid - 1, optHi); j++) {
if (prev[j] >= INF) continue;
ll val = prev[j] + cost(j, mid);
if (val < best) { best = val; bestJ = j; }
}
cur[mid] = best;
solve(lo, mid - 1, optLo, bestJ);
solve(mid + 1, hi, bestJ, optHi);
}
ll run(const vector<ll>& a, int k) {
int n = (int)a.size();
S.assign(n + 1, 0);
for (int i = 0; i < n; i++) S[i + 1] = S[i] + a[i];
prev.assign(n + 1, INF);
prev[0] = 0;
for (int g = 1; g <= k; g++) {
cur.assign(n + 1, INF);
solve(g, n, g - 1, n - 1);
swap(prev, cur);
}
return prev[n];
}
};
ll minSquaredPartitionNaive(const vector<ll>& a, int k) {
int n = (int)a.size();
vector<ll> S(n + 1, 0), p(n + 1, INF);
for (int i = 0; i < n; i++) S[i + 1] = S[i] + a[i];
p[0] = 0;
for (int g = 1; g <= k; g++) {
vector<ll> c(n + 1, INF);
for (int i = g; i <= n; i++)
for (int j = g - 1; j < i; j++)
if (p[j] < INF) c[i] = min(c[i], p[j] + (S[i] - S[j]) * (S[i] - S[j]));
p = c;
}
return p[n];
}
uint64_t seed = 99;
int nextInt(int bound) {
seed = seed * 48271 % 2147483647ULL;
return (int)(seed % bound);
}
int main() {
vector<ll> example{3, 1, 4, 1, 5, 9, 2, 6};
Partitioner P;
assert(P.run(example, 3) == 341 && minSquaredPartitionNaive(example, 3) == 341);
for (int t = 0; t < 400; t++) {
int n = 1 + nextInt(30);
vector<ll> a(n);
for (int i = 0; i < n; i++) a[i] = nextInt(50);
int k = 1 + nextInt(n);
assert(P.run(a, k) == minSquaredPartitionNaive(a, k));
}
cout << "dnc ok " << P.run(example, 3) << "\n";
}
// Divide & conquer optimisation: split a (values >= 0) into exactly k non-empty
// contiguous groups, minimising the sum of (group sum)^2.
// dp[g][i] = min_{g-1 <= j < i} dp[g-1][j] + (S[i] - S[j])^2, opt monotone in i.
function minSquaredPartition(a: number[], k: number): number {
const n = a.length;
const S = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) S[i + 1] = S[i] + a[i];
let prev = new Array<number>(n + 1).fill(Infinity);
prev[0] = 0;
let cur: number[] = [];
const solve = (lo: number, hi: number, optLo: number, optHi: number): void => {
if (lo > hi) return;
const mid = (lo + hi) >> 1;
let best = Infinity, bestJ = optLo;
for (let j = optLo; j <= Math.min(mid - 1, optHi); j++) {
const val = prev[j] + (S[mid] - S[j]) ** 2;
if (val < best) { best = val; bestJ = j; }
}
cur[mid] = best;
solve(lo, mid - 1, optLo, bestJ);
solve(mid + 1, hi, bestJ, optHi);
};
for (let g = 1; g <= k; g++) {
cur = new Array<number>(n + 1).fill(Infinity);
solve(g, n, g - 1, n - 1);
prev = cur;
}
return prev[n];
}
function minSquaredPartitionNaive(a: number[], k: number): number {
const n = a.length;
const S = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) S[i + 1] = S[i] + a[i];
let p = new Array<number>(n + 1).fill(Infinity);
p[0] = 0;
for (let g = 1; g <= k; g++) {
const c = new Array<number>(n + 1).fill(Infinity);
for (let i = g; i <= n; i++)
for (let j = g - 1; j < i; j++) c[i] = Math.min(c[i], p[j] + (S[i] - S[j]) ** 2);
p = c;
}
return p[n];
}
let seed = 99;
function nextInt(bound: number): number {
seed = (seed * 48271) % 2147483647;
return seed % bound;
}
function assert(cond: boolean, msg = "assertion failed"): void {
if (!cond) throw new Error(msg);
}
const example = [3, 1, 4, 1, 5, 9, 2, 6];
assert(minSquaredPartition(example, 3) === 341 && minSquaredPartitionNaive(example, 3) === 341);
for (let t = 0; t < 400; t++) {
const n = 1 + nextInt(30);
const a: number[] = [];
for (let i = 0; i < n; i++) a.push(nextInt(50));
const k = 1 + nextInt(n);
assert(minSquaredPartition(a, k) === minSquaredPartitionNaive(a, k), "mismatch");
}
console.log("dnc ok " + minSquaredPartition(example, 3));
Unreachable states
With "exactly non-empty groups", is undefined for . The code starts each layer at with candidates , so it never reads an infinite value as a real one. The Java and C++ versions also skip INF explicitly so INF + cost cannot overflow.
6. Knuth's optimisation
When it applies. An interval DP of the form
which is : intervals, split points each. Classic members: merging adjacent piles of stones where a merge costs the total weight (AtCoder DP N "Slimes", CSES "Knuth Division"), and the optimal binary search tree, Knuth's original problem.
The condition. Let be the best split . Knuth's optimisation uses
Yao (1980) proved that this holds whenever satisfies
- the quadrangle inequality for , and
- monotonicity on the lattice of intervals: whenever .
For stone merging, . The QI holds with equality (both sides add up the same elements), and monotonicity holds because weights are non-negative.
The idea. Process intervals by increasing length. When you get to , the two neighbours and are shorter and already have their values. Scan only (clamped to ).
Why . Fix a length . The scan for costs . Summing over , the terms telescope: each added for one interval is subtracted for the next. The total for one length is at most . Over lengths: .
Trace on piles ():
| Interval | Allowed | Options | ||
|---|---|---|---|---|
| [0,1] | [0, 0] | 0 + 0, +30 | 30 | 0 |
| [1,2] | [1, 1] | +50 | 50 | 1 |
| [2,3] | [2, 2] | +70 | 70 | 2 |
| [0,2] | [opt[0][1], opt[1][2]] = [0, 1] | : 0 + 50; : 30 + 0; then +60 | 90 | 1 |
| [1,3] | [1, 2] | : 0 + 70; : 50 + 0; then +90 | 140 | 2 |
| [0,3] | [opt[0][2], opt[1][3]] = [1, 2] | : 30 + 70; : 90 + 0; then +100 | 190 | 2 |
The full interval scans only 2 split points instead of 3. Small here; on 300 random piles the naive DP evaluated split points and Knuth's version — 50× fewer, with identical answers.
# Knuth's optimisation: merge adjacent piles (AtCoder DP N "Slimes").
# dp[i][j] = min over i <= m < j of dp[i][m] + dp[m+1][j] + (sum of a[i..j])
# opt[i][j-1] <= opt[i][j] <= opt[i+1][j] -> O(n^2) total.
import random
def merge_naive(a):
n = len(a)
S = [0] * (n + 1)
for i, v in enumerate(a):
S[i + 1] = S[i] + v
dp = [[0] * n for _ in range(n)]
work = 0
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
best = None
for m in range(i, j):
work += 1
val = dp[i][m] + dp[m + 1][j]
if best is None or val < best:
best = val
dp[i][j] = best + S[j + 1] - S[i]
return dp[0][n - 1], work
def merge_knuth(a):
n = len(a)
S = [0] * (n + 1)
for i, v in enumerate(a):
S[i + 1] = S[i] + v
dp = [[0] * n for _ in range(n)]
opt = [[0] * n for _ in range(n)]
for i in range(n):
opt[i][i] = i
work = 0
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
best, best_m = None, -1
for m in range(opt[i][j - 1], min(j - 1, opt[i + 1][j]) + 1):
work += 1
val = dp[i][m] + dp[m + 1][j]
if best is None or val < best:
best, best_m = val, m
dp[i][j] = best + S[j + 1] - S[i]
opt[i][j] = best_m
return dp[0][n - 1], work
assert merge_naive([10, 20, 30, 40])[0] == merge_knuth([10, 20, 30, 40])[0] == 190
rng = random.Random(1971)
for _ in range(1000):
a = [rng.randint(1, 100) for _ in range(rng.randint(1, 25))]
assert merge_naive(a)[0] == merge_knuth(a)[0]
big = [rng.randint(1, 10**6) for _ in range(300)]
(v1, w1), (v2, w2) = merge_naive(big), merge_knuth(big)
assert v1 == v2
print("knuth ok", w1, w2)
Knuth is not divide and conquer
Both use "opt is monotone", but on different recurrences. Knuth needs the interval form with both neighbours' available and gives . Divide and conquer needs a layered form and gives . Some layered DPs satisfy a Knuth-style bound too, which gives for all layers together (cp-algorithms describes this variant); test it before relying on it.
7. The Aliens trick (Lagrangian relaxation, WQS binary search)
When it applies. The problem says "use exactly " (or "at most ") of something — groups, transactions, open stations — and the natural DP carries as a dimension, costing or worse. The trick removes that dimension.
The name comes from the IOI 2016 problem "Aliens", whose full solution needed it; the method is also called WQS binary search after Wang Qinshi, who described it in a 2012 Chinese training paper, and it is an instance of Lagrangian relaxation from optimisation theory. (The attribution to Wang Qinshi is the one used across the competitive-programming literature; I have not seen the original paper.)
The condition. Let be the optimal answer with exactly items. The trick needs to be concave in for a maximisation (the gain from each extra item never increases: ), or convex for a minimisation.
The idea. Instead of limiting the count, charge a penalty for every item and drop the limit:
Computing is a DP without the dimension; it also reports how many items its optimum used, . Geometrically, plot the points . They form a concave chain. Sliding a line of slope down onto the chain, it first touches the point where the chain's slope crosses — that is . A large penalty makes the optimum use fewer items; a small one, more. Binary-search until , then undo the penalty: .
The tie subtlety. Several can be optimal for the same (when the chain has several points on one line). The robust recipe: break ties toward the fewest items, find the smallest with , and return . Because is also optimal at that (it lies on the same supporting line), the formula is exact even when . With integer data the slopes are integers, so integer suffices.
Example: Best Time to Buy and Sell Stock IV (LeetCode 188). At most buy-sell transactions; maximise profit. The textbook DP is . Max profit is concave in (it is a min-cost-flow value, and successive augmenting paths in min-cost flow have non-increasing gains), so: charge per buy, run the two-state DP (free, hold) with tie-break toward fewer buys, binary-search . Total .
On prices : . The gains are : concave.
| (fewest) | ||
|---|---|---|
| 0 | 7 | 2 |
| 1 | 5 | 2 |
| 2 | 3 | 2 |
| 3 | 1 | 1 |
| 4 | 0 | 0 |
For : the smallest with is 3, so (buy at 2, sell at 6). At both and score (): a tie, which is why we broke ties toward fewer buys. For : already gives , so .
# Aliens trick (WQS binary search / Lagrangian relaxation) on
# LeetCode 188 "Best Time to Buy and Sell Stock IV": at most k transactions.
import random
def stock_k_naive(prices, k): # O(n * k)
free = [0] * (k + 1) # free[t]: best profit, not holding, t buys used
hold = [float("-inf")] * (k + 1) # hold[t]: best profit, holding, t buys used
for p in prices:
for t in range(k, 0, -1):
free[t] = max(free[t], hold[t] + p)
hold[t] = max(hold[t], free[t - 1] - p)
return max(free)
def penalised(prices, lam):
"""Best (profit - lam * buys), with no limit on buys. Ties -> fewer buys.
Returns (penalised value, number of buys)."""
free = (0, 0) # (value, -buys): max() prefers fewer buys on ties
hold = (float("-inf"), 0)
for p in prices:
new_free = max(free, (hold[0] + p, hold[1]))
new_hold = max(hold, (free[0] - p - lam, free[1] - 1))
free, hold = new_free, new_hold
return free[0], -free[1]
def stock_k_aliens(prices, k): # O(n log maxPrice)
lo, hi = 0, max(prices, default=0) + 1 # at lam = max price + 1 no trade is worth it
while lo < hi: # smallest lam whose optimum uses <= k buys
mid = (lo + hi) // 2
if penalised(prices, mid)[1] <= k:
hi = mid
else:
lo = mid + 1
value, _ = penalised(prices, lo)
return value + lo * k
assert stock_k_aliens([3, 2, 6, 5, 0, 3], 2) == stock_k_naive([3, 2, 6, 5, 0, 3], 2) == 7
assert stock_k_aliens([2, 4, 1], 2) == 2
rng = random.Random(2016)
for _ in range(3000):
prices = [rng.randint(0, 30) for _ in range(rng.randint(0, 25))]
k = rng.randint(0, 8)
assert stock_k_aliens(prices, k) == stock_k_naive(prices, k), (prices, k)
print("aliens ok")
Check concavity before you use it
Without concavity, some is never optimal for any (the point lies strictly below the hull of the chain), and the binary search silently returns the value of the hull, not . Prove concavity (exchange argument, flow argument, or a known matroid structure) or at least test it: compute with the slow DP on many random inputs and check that the differences never increase.
8. Bitset optimisation
When it applies. A boolean DP where each step transforms the whole row of states by a shift and an OR (or AND, XOR). Subset sum is the poster child: ok[s] = "some subset of the items so far sums to ", and adding item does ok[s] |= ok[s - x] for every .
The condition. The row update must be the same simple bit operation for every position, so that it can be done on 64 positions at once.
The idea. Store the row as bits of machine words. "For every , ok[s] |= ok[s - x]" is exactly reach |= reach << x. A CPU does that 64 bits per instruction (more with SIMD), so the cost drops from to with . It is still the same asymptotic class, but a 64× constant is often the difference between 10 seconds and 0.2 seconds. Python's arbitrary-precision integers do the same thing internally (CPython stores them as arrays of 30-bit digits); C++ has std::bitset<N> and Java has java.util.BitSet (whose shifts you write by hand on its long[]).
# Bitset optimisation for subset sum: bit s of `reach` is 1 iff some subset sums to s.
# reach |= reach << x processes one item for all sums at once (word-parallel).
import random
def subset_sums_naive(nums, target): # O(n * target) booleans
ok = [True] + [False] * target
for x in nums:
for s in range(target, x - 1, -1):
ok[s] = ok[s] or ok[s - x]
return ok
def subset_sums_bitset(nums, target): # O(n * target / w) word operations
reach = 1 # only the empty sum 0
mask = (1 << (target + 1)) - 1
for x in nums:
reach = (reach | (reach << x)) & mask
return [(reach >> s) & 1 == 1 for s in range(target + 1)]
def can_partition(nums): # LeetCode 416
total = sum(nums)
if total % 2:
return False
reach = 1
for x in nums:
reach |= reach << x
return (reach >> (total // 2)) & 1 == 1
assert subset_sums_bitset([3, 34, 4, 12, 5, 2], 9)[9]
assert can_partition([1, 5, 11, 5]) and not can_partition([1, 2, 3, 5])
rng = random.Random(416)
for _ in range(500):
nums = [rng.randint(1, 40) for _ in range(rng.randint(0, 15))]
t = rng.randint(0, 200)
assert subset_sums_bitset(nums, t) == subset_sums_naive(nums, t)
print("bitset ok")
#include <bitset>
#include <cassert>
#include <iostream>
#include <vector>
// LeetCode 416 with std::bitset: sums up to 100 * 200 = 20000.
bool canPartition(const std::vector<int>& nums) {
int total = 0;
for (int x : nums) total += x;
if (total % 2) return false;
std::bitset<20001> reach;
reach[0] = 1;
for (int x : nums) reach |= reach << x; // 20001 / 64 = 313 word operations per item
return reach[total / 2];
}
int main() {
assert(canPartition({1, 5, 11, 5}));
assert(!canPartition({1, 2, 3, 5}));
std::cout << "bitset ok\n";
}
The same word-level parallelism powers Myers' bit-vector edit-distance algorithm (Myers, "A fast bit-vector algorithm for approximate string matching based on dynamic programming", JACM 46(3), 1999), which computes 64 cells of the edit-distance table per instruction and is used in aligners such as Edlib.
The ladder: brute force → better → optimal
Take one problem and climb: Frog 3 (CHT) with .
Rung 1: recursion without memo
Try every subset of stones to land on: routes. Hopeless beyond .
Rung 2: the naive DP,
. Correct, simple, operations for : minutes, not seconds. Keep it — it is your test oracle.
Rung 3: notice the shape
Expand the square. The mixed term is : a product of a -part and an -part. That is a line.
Rung 4: Li Chao tree,
Works without thinking about order. steps.
Rung 5: monotone deque CHT,
Heights are increasing, so slopes decrease and queries increase: amortised per stone.
| Technique | Removes | Before → after | Needs |
|---|---|---|---|
| Prefix sums | the loop of a range sum | contiguous range | |
| Monotonic queue | the loop of a window min/max | -only key, sliding window | |
| CHT (deque) | the min over lines | sorted slopes and queries | |
| CHT (binary search) | same | sorted slopes only | |
| Li Chao tree | same | nothing about order | |
| Divide & conquer | the min over split points, per layer | monotone (QI) | |
| Knuth | the min over split points, interval DP | QI + monotone | |
| Aliens | the count dimension | concave/convex in | |
| Bitset | 64 boolean states at once | uniform bit operation |
Correctness
Each technique computes the same minimum as the naive DP; what needs proof is that the candidates it skips could never win.
Prefix sums. by the definition of — exact arithmetic, nothing skipped. (Under a modulus the identity holds modulo .)
Monotonic queue. Invariant: the deque contains, in increasing index order, exactly the indices in the current window that are not dominated, where is dominated if some later in the window has (for a max). Dominated indices can never be the unique best: is at least as good and leaves the window later. Popping from the back when a new better key arrives and from the front when an index expires maintains the invariant, and the keys in the deque are strictly decreasing, so the front is the maximum. Each index is pushed and popped at most once: total.
CHT with a deque. Invariant: the deque holds, by decreasing slope, exactly the lines that appear on the lower envelope of all lines inserted so far, restricted to the last query. (a) Adding. A new line has the smallest slope, so it is lowest for all sufficiently large and belongs at the right end. The back line (with predecessor ) is on the new envelope iff some has below both and ; since beats exactly for and beats exactly for , such exists iff , which is equivalent to . Otherwise it is useless forever; pop and repeat. (b) Querying. If the second line is at most the first at , it is at most the first for every larger (it has the smaller slope), and queries never decrease; so the first line can never again be the unique minimum. Pop it. Then the first line is the minimum at , because envelope segments appear left to right in deque order.
Li Chao tree. Invariant: for every and every inserted line , some node on the root-to-leaf path of stores a line whose value at is . Insert preserves it: at each node, the line kept is at least as low at ; the loser and the winner cross at most once, so on one half (the one not containing the crossing) everywhere, and is pushed into the other half, where the argument repeats. If the recursion ends at a leaf, the leaf keeps the better of the two at its single point. So the minimum over the path is the minimum over all lines.
Divide-and-conquer (opt is monotone under QI). Let and let be the smallest minimiser of . Suppose but . Then . Because is the smallest minimiser for and : . Because is a minimiser for : . Add the two and cancel :
But QI with says . Contradiction. So is non-decreasing, and restricting 's neighbours to and never excludes an optimum. Note that the proof never used anything about : the previous layer can be arbitrary.
Knuth. Yao's proof has two lemmas. (1) If satisfies QI and is monotone on intervals, then itself satisfies QI. This is an induction on , splitting at the optimal points and recombining the pieces (CLRS-style cut-and-paste; see Yao 1980 or the cp-algorithms article for the full case analysis). (2) If satisfies QI, then — an exchange argument of exactly the same shape as the divide-and-conquer proof above, applied to the split point. I give the second lemma's shape here and refer to Yao for the first; it is long but elementary.
Aliens. For a fixed , for every by definition, with equality for the maximisers. Because is concave, for every there is a (any value between the slopes and ) for which is a maximiser — the line of slope through supports the chain. At that , . The set of maximisers at is a contiguous range , and is non-increasing in ; the smallest with has inside its range (for integer slopes and integer ), so the formula applies.
Bitset. reach << x sets bit iff bit was set; OR-ing implements ok[s] |= ok[s-x] for all simultaneously. Because the shift reads the old word values, each item is used at most once — the bitset version automatically has 0/1-knapsack semantics, with no reverse loop needed.
Complexity
| Technique | Time | Extra space | Notes |
|---|---|---|---|
| Prefix sums | per state | (or per row) | plus building |
| Monotonic queue | total, amortised | each index in/out once | |
| CHT, monotone deque | total (after sorting) | amortised; worst single step | |
| CHT, sorted slopes, arbitrary queries | binary search on the hull | ||
| Dynamic hull (line container) | amortised per op | ordered set of lines | |
| Li Chao tree | per insert/query | array, or dynamic | = size of the -domain |
| Li Chao, segments | per insert | as above | segment splits into nodes |
| D&C optimisation | per two layers | cost must be to evaluate | |
| Knuth | telescoping sum | ||
| Aliens | that of the inner DP | = penalised DP, = range of | |
| Bitset | words | ; SIMD helps further |
Constants matter. The deque CHT and the monotonic queue are among the fastest code you will write. Li Chao is slower per operation (a and cache misses) but has the fewest bugs. Divide and conquer has small constants but needs in — precompute prefix sums. For costs that are expensive to evaluate but can be updated incrementally (like "number of distinct values in the segment"), a two-pointer cost evaluator that moves like Mo's algorithm keeps D&C at amortised (Codeforces 868F "Yet Another Minimization Problem" is the standard exercise).
Implementation notes
The four-language programs above (CHT, Li Chao, D&C) are complete and self-testing. A few practical notes:
- Always keep the naive DP. In contests and in production, the optimised DP should be tested against it on thousands of random small inputs. Every program in this lesson does this. It costs ten lines.
- Use integers. Floating-point crossing points break on near-ties. Cross-multiply, and widen to 128 bits (
__int128,Math.multiplyHigh,BigInt) if products can exceed . - Choose a tie rule and stick to it. D&C and Knuth are correct with any consistent choice of under the conditions above, but mixing "first minimum" in one place and "last minimum" in another can break monotonicity on plateaus. Aliens needs a specific rule (fewest items).
- Recursion depth. D&C recursion depth is , so recursion is safe. Knuth and CHT are iterative.
- Reconstruction. All the techniques can record (or the chosen line's index) per state, so you can reconstruct the actual solution exactly as in a naive DP. For Aliens, reconstruction is harder: the penalised DP's solution may use items when there are ties; fixing it up requires extra work (see the "Aliens reconstruction" discussions on Codeforces).
Real-world uses
- Line breaking in typesetting. Knuth and Plass's algorithm in TeX ("Breaking paragraphs into lines", Software: Practice and Experience 11(11), 1981) is a DP over breakpoints; its practical speed comes from pruning infeasible breakpoints. When the badness is a convex function of the line's slack (for example the squared slack used in "minimum raggedness"), the recurrence has the quadrangle-inequality structure and can be solved in or even (Hirschberg and Larmore, "The least weight subsequence problem", SIAM J. Computing 16(4), 1987; Wilber, "The concave least-weight subsequence problem revisited", J. Algorithms 9, 1988). The DP capstone builds the plain version.
- Optimal 1-D clustering and natural breaks. Optimal -means in one dimension on sorted data is a layered partition DP whose within-cluster sum of squares satisfies the quadrangle inequality. The R package Ckmeans.1d.dp (Wang and Song, The R Journal 3(2), 2011) started as the DP and later versions adopted faster algorithms built on the same monotonicity; Grønlund et al. ("Fast exact k-means, k-medians and Bregman divergence clustering in 1D", 2017, arXiv:1701.07204) give with SMAWK. Jenks natural-breaks classification, used to colour choropleth maps in GIS tools, optimises the same objective.
- Histogram construction for query optimisers. V-optimal histograms partition a column's value distribution into buckets minimising squared error with an DP (Jagadish et al., "Optimal Histograms with Quality Guarantees", VLDB 1998) — the same layered shape that D&C optimisation targets.
- Optimal binary search trees. Knuth's 1971 paper introduced the speed-up for exactly this: a static search tree with known access frequencies (a dictionary, a symbol table) built in instead of .
- Rate-distortion optimisation in video encoders. Encoders choose per-block modes to minimise distortion subject to a bit budget . Instead of a budget dimension, they minimise for a Lagrange multiplier — exactly the Aliens idea (Sullivan and Wiegand, "Rate-distortion optimization for video compression", IEEE Signal Processing Magazine 15(6), 1998). Lagrangian relaxation is also a workhorse of operations research (Held and Karp's 1-tree bounds for the TSP, 1970–71).
- Bit-parallel string matching. Myers' bit-vector edit distance (1999) and the Shift-And / Bitap family (Baeza-Yates and Gonnet, 1992; Wu and Manber's
agrep, 1992) run DPs on machine words, 64 cells at a time — the bitset idea in production. - Competitive programming. Honestly, the convex hull trick, Li Chao trees and Aliens are mostly seen in contests (IOI 2016 "Aliens", IOI 2014 "Holiday", APIO 2014 "Sequence" are well-known examples). Their value outside contests is in recognising the same structures — lower envelopes, Monge matrices, Lagrange multipliers — in geometry, scheduling and optimisation code.
Pitfalls & edge cases
- Using a technique whose condition does not hold. The optimised DP will usually still return a number — just a wrong one. Test against the naive DP on random inputs, including negative values and duplicates if the input allows them.
- D&C/Knuth with negative values. The quadrangle inequality for "(sum of group)" relies on non-negative elements. With negatives, need not be monotone.
- Equal slopes in CHT. Two lines with the same slope make the crossing-point formula divide by zero. Keep only the lower one (for a min) before running the "useless" test, or break the strict-decrease assumption explicitly.
- Wrong direction. Min with increasing slopes, max with decreasing slopes — each flips which end of the deque the new line goes to. Transform to the one case you trust (, or negate everything).
- Li Chao domain. Queries outside silently go to the wrong leaf. Compress coordinates if the query points are known offline, or use a dynamic tree over the full range.
- Overflow in cross-multiplication, in
INF + cost, and in squared prefix sums. Use a sentinel likeLLONG_MAX / 4and skip unreachable states. - Aliens ties. Without a consistent tie-break toward fewer (or more) items, the binary search can oscillate around and never hit it exactly. Use the "smallest with " rule and add back , not .
- Aliens range of . It must cover all slopes of : from below the smallest marginal gain to above the largest. For integer data, integer is enough; for real-valued costs, binary search on reals for a fixed number of iterations.
- Monotonic queue: expire before you read. Pop indices that left the window from the front before using the front. And decide whether the window includes or not; off-by-one here is the classic bug.
- Bitset size.
std::bitsetneeds a compile-time size; choose the maximum possible sum. Shifting beyond it silently drops bits, which is what you want for "sums above target are useless".
Variations
- Dynamic CHT ("line container"). An ordered set of lines keyed by slope, with each line storing the where it stops being optimal; insertion removes neighbours that became useless. amortised per operation, no order requirements, real-valued queries. KACTL's
LineContaineris a well-known compact implementation. - CHT with binary-search queries. Slopes sorted, queries arbitrary: keep the hull in an array and binary search for the segment containing .
- Kinetic segment trees and Li Chao on segments. Lines valid only on an interval of .
- SMAWK and totally monotone matrices. If the matrix is totally monotone, all row minima can be found in (Aggarwal et al., 1987). D&C is the , easy-to-code version of the same idea.
- 1D/1D online optimisation with a deque of candidate intervals. When depends on of the same layer and the cost satisfies QI, maintain a stack/deque of ranges where is the best predecessor, with binary search on boundaries: (Galil and Park, 1992 survey "Dynamic programming with convexity, concavity and sparsity").
- Slope trick. When is a convex piecewise-linear function of a parameter, store its breakpoints in a heap and transform the whole function in per step (Codeforces 713C "Sonya and Problem Wihtout a Legend" is the standard example).
- Sum-over-subsets DP. A different kind of optimisation, for transitions over all subsets of a mask; see SOS DP.
- Matrix exponentiation. For linear recurrences with a huge and a small state, see Matrix Exponentiation.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Number of Dice Rolls With Target Sum (LeetCode 1155) — Count the ways dice with faces add up to a target. Teaches the sliding-sum speed-up.
Hint
The last die covers a window of totals of the previous row. The prefix-sum code in section 1 is a full solution.
2. New 21 Game (LeetCode 837) — Draw uniform card values until your score reaches a threshold; find the probability of finishing at or below a limit. Teaches a running window sum on probabilities.
Hint
P[x] = (P[x-1] + … + P[x-W]) / W, but only counting predecessors that were still drawing (below the threshold). Keep one running sum.
3. Jump Game VI (LeetCode 1696) — Jump at most steps at a time, collecting the values you land on; maximise the total. Teaches the monotonic-queue DP in its purest form.
Hint
dp[i] = nums[i] + max(dp[i-k..i-1]) — a sliding window maximum over the DP array.
4. Constrained Subsequence Sum (LeetCode 1425) — Maximum-sum subsequence whose consecutive chosen indices are at most apart. Teaches the "max(0, …)" restart plus a monotonic queue.
Solution
best[i] = nums[i] + max(0, max(best[i-k..i-1])), answer max(best). Keep a deque of indices with strictly decreasing best; expire the front when it leaves the window, pop the back while it is no better than the new value. time, space. The constrained_deque function in section 2 is a full solution and is tested against the DP.
5. Partition Equal Subset Sum (LeetCode 416) — Can the array be split into two parts of equal sum? Teaches the bitset subset sum.
Solution
If the total is odd, no. Otherwise check whether some subset reaches half the total: start with reach = 1 (bit 0) and do reach |= reach << x for every element; test bit total / 2. With at most 200 numbers of value at most 100, a std::bitset<20001> needs 313 words per item. can_partition in section 8 is a full solution.
6. Frog 3 (AtCoder Educational DP Contest, problem Z) — Hop forward along stones of increasing height; a hop costs the squared height difference plus a constant. Teaches the convex hull trick with a monotone deque.
Solution
Expand : stone is the line with slope and intercept , queried at . Heights increase, so slopes decrease and queries increase. The frog3_cht code in section 3 is a full solution; read , and the heights from standard input and print frog3_cht(h, C). Heights up to make the cross-multiplied test approach , so use 128-bit arithmetic in C++ (as shown) or Python's big integers.
7. Slimes (AtCoder Educational DP Contest, problem N) — Merge adjacent slimes until one remains, paying the combined size each time; minimise the total. Teaches interval DP, with Knuth as the upgrade.
Hint
With the interval DP passes. Implement Knuth's version anyway and compare the number of split points scanned; section 6 has the code.
8. Monster Game I (CSES 2084) — Each level's cost is your current skill factor times the monster's strength; killing a monster gives you its factor. The input guarantees both sequences are sorted. Teaches CHT with sorted slopes and queries.
Hint
dp[i] = min_j dp[j] + s_j · f_i, with the starting skill as an extra line of intercept 0. Check which direction the slopes and queries are sorted in before choosing the deque end.
9. Monster Game II (CSES 2085) — The same game without the sortedness guarantees. Teaches the Li Chao tree.
Hint
The monster_game_lichao function in section 4 is exactly this recurrence; size the tree to the range of strengths (), or compress coordinates.
10. Subarray Squares (CSES 2086) — Split an array of positive numbers into contiguous pieces minimising the sum of squared piece sums. Teaches divide-and-conquer optimisation.
Solution
Exactly the worked example of section 5: , cost satisfies the quadrangle inequality because the values are positive. With and , is about cheap operations in C++. Use 64-bit integers: with the limits stated at the time of writing (, values up to ) the total is at most and its square , which fits in a signed 64-bit integer. The Partitioner C++ code above is a full solution once you read the input.
11. Knuth Division (CSES 2088) — Repeatedly cut an array into two parts until every element stands alone, paying the sum of the part being cut each time; minimise the total. Teaches Knuth's optimisation on the reversed stone-merging DP.
Hint
Cutting from the top down costs the same as merging from the bottom up. Use merge_knuth from section 6 with : .
12. Kalila and Dimna in the Logging Industry (Codeforces 319C) — Cut trees in an order that minimises total recharging cost; the cost of a cut depends on the height and on the most recently finished tree. Teaches spotting the line after a modelling step.
Hint
Once the last (tallest index) tree is cut everything is free, so dp[i] = min_j dp[j] + b_j · a_i. decreases and increases: monotone deque CHT.
13. Ciel and Gondolas (Codeforces 321E) — Split a queue of people into consecutive groups minimising total unfamiliarity within groups. Teaches D&C optimisation with a 2-D prefix-sum cost, and fast input.
Hint
Cost of a group = half the sum of the unfamiliarity submatrix, with 2-D prefix sums. The cost satisfies the quadrangle inequality because entries are non-negative.
14. Best Time to Buy and Sell Stock IV (LeetCode 188) — At most transactions; maximise profit. Teaches the Aliens trick on an easy-to-verify problem.
Solution
Either the two-array DP, or Aliens: charge per buy, run the two-state free/hold DP preferring fewer buys on ties, and binary-search the smallest whose optimum uses at most buys; return value . stock_k_aliens in section 7 is a full solution, tested against the DP on 3,000 random cases.
15. Aliens (IOI 2016, on oj.uz) — Cover marked cells of a grid with at most squares centred on the diagonal, minimising the covered area. Teaches the full stack: reduction to intervals, CHT for the inner DP, Aliens for the constraint.
Hint
Reduce each point to an interval on the diagonal, drop intervals contained in others, sort. The inner DP is a squared-cost partition (CHT). The area is convex in the number of squares, so wrap it in a binary search on the penalty.
Common mistakes & interview follow-ups
"Why can't you just use a monotonic queue for Frog 3?" Because whether beats depends on : the key mixes the two. A monotonic queue needs a key that depends on alone. The mixed part is linear in , which is why lines (CHT) are the right tool.
"How do you know the quadrangle inequality holds?" For costs built from prefix sums, expand and factor, as in section 5. For other costs, a sufficient check is: is a convex function of a monotone quantity of the segment. If you cannot prove it, compute with the naive DP on random inputs and assert monotonicity. Say this in an interview: it shows you know the condition is the hard part.
"Divide and conquer or Knuth?" Layered recurrence ( from ) → D&C. Interval recurrence ( from sub-intervals) → Knuth. If is large (close to ), D&C's is worse than ; then consider Knuth's layered variant or Aliens.
"What if slopes are not sorted?" Li Chao tree, or a dynamic line container, or sort offline and use CDQ divide and conquer (process the left half, build a hull from it, answer the right half's queries).
"Is the Aliens answer always exact?" Only if is concave (or convex). Otherwise you get the value of the concave hull of at , which is an upper bound for a max.
Mistakes interviewers watch for: forgetting to separate the -only terms out of the min; overflow in cross products; using floating-point intersection points; querying a Li Chao tree outside its domain; not handling unreachable states in layered DPs; applying D&C to a cost with negative values; returning instead of .
Quick quiz
1. . Which technique, and why?
Answer
Monotonic queue. The key depends only on , and comes out of the min. The window slides.
2. with unsorted. Which technique?
Answer
Expand: lines with slope , queried at . Neither slopes nor queries are sorted, so use a Li Chao tree (or a dynamic line container).
3. In the Frog 3 trace, why was stone 1's line removed when stone 2's line arrived, even though no query had been made at yet?
Answer
Because overtakes at , before would overtake at . So is never strictly lowest for any , now or later — lines are never removed from the set, only added, and additions can only push further from the envelope.
4. Does satisfy the quadrangle inequality?
Answer
Yes. It is the cost with all elements equal to 1, so the identity in section 5 gives a difference of .
5. What does buy you, in one sentence?
Answer
The total number of split points scanned per diagonal telescopes to , so the interval DP drops from to .
6. For prices , which does the Aliens binary search stop at for , and what is the answer?
Answer
(with ties broken toward fewer buys, and ). , so the answer is .
7. Why does reach |= reach << x not reuse item twice, while the forward loop for s in 0..S: ok[s] |= ok[s-x] does?
Answer
The shift reads the whole old bitset before any bit is written, so every new bit depends only on the state before this item. The forward loop reads ok[s-x] that may already have been updated in this same pass.
Further reading / sources
- cp-algorithms: Convex hull trick and Li Chao tree, Divide and Conquer DP, Knuth's Optimization.
- Donald E. Knuth, "Optimum binary search trees", Acta Informatica 1(1), 14–25, 1971 — the original speed-up.
- F. Frances Yao, "Efficient dynamic programming using quadrangle inequalities", Proceedings of the 12th ACM STOC, 429–435, 1980 — the Knuth–Yao conditions. See also Yao, "Speed-up in dynamic programming", SIAM J. Algebraic and Discrete Methods 3(4), 1982.
- A. Aggarwal, M. Klawe, S. Moran, P. Shor, R. Wilber, "Geometric applications of a matrix-searching algorithm", Algorithmica 2, 1987 — SMAWK and totally monotone matrices.
- Zvi Galil and Kunsoo Park, "Dynamic programming with convexity, concavity and sparsity", Theoretical Computer Science 92(1), 1992 — a survey of these speed-ups.
- D. S. Hirschberg and L. L. Larmore, "The least weight subsequence problem", SIAM J. Computing 16(4), 1987.
- Gene Myers, "A fast bit-vector algorithm for approximate string matching based on dynamic programming", Journal of the ACM 46(3), 1999.
- IOI 2016 problem "Aliens" and its editorial — the origin of the trick's competitive-programming name.
- AtCoder Educational DP Contest, problem list; CSES Problem Set, "Advanced Techniques" section.
Lessons: previous — Matrix Exponentiation · next — DP Debugging · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Monotonic Stack & Deque · Prefix Sums · Segment Trees · Binary Search · Interval DP · Partition DP · Knapsack · Grid & Path DP · String DP.