Divide and Conquer DP

Optimise a recurrence of the form

$dp[i][j]={\min }_{k\le j}(dp[i-1][k]+C(k,j))$

from $O(k{n}^2)$ to $O(kn\log n)$, when the optimal split point is monotone:

$\mathrm{opt}[i][j]\le \mathrm{opt}[i][j+1].$

The algorithm

For a fixed layer $i$, solve the range $[l,r]$ knowing $\mathrm{opt}$ lies in $[\mathrm{optL},\mathrm{optR}]$:

1. Take the midpoint $m=(l+r)/2$.
2. Compute $dp[i][m]$ by scanning $k\in [\mathrm{optL},\min (m,\mathrm{optR})]$, recording the argmin ${\mathrm{opt}}_m$.
3. Recurse on $[l,m-1]$ with the range $[\mathrm{optL},{\mathrm{opt}}_m]$ and on $[m+1,r]$ with $[{\mathrm{opt}}_m,\mathrm{optR}]$.

vector<long long> prev_, cur;
 
void compute(int l, int r, int optL, int optR) {
    if (l > r) return;
    int m = (l + r) / 2;
    pair<long long,int> best = {LLONG_MAX, -1};
    for (int k = optL; k <= min(m, optR); k++)
        best = min(best, {prev_[k] + C(k, m), k});
    cur[m] = best.first;
    int opt = best.second;
    compute(l, m - 1, optL, opt);
    compute(m + 1, r, opt, optR);
}
 
long long solve(int n, int layers) {
    prev_ = baseLayer(n);
    for (int i = 1; i <= layers; i++) {
        cur.assign(n + 1, LLONG_MAX);
        compute(0, n, 0, n);
        swap(prev_, cur);
    }
    return prev_[n];
}

Complexity: $O(\log n)$ recursion levels, and at each level the scanned $k$-ranges overlap only at their endpoints, totalling $O(n)$ work. So $O(n\log n)$ per layer, $O(kn\log n)$ overall.

When does monotonicity hold?

Sufficient condition: $C$ satisfies the quadrangle inequality (concave Monge)

$C(a,c)+C(b,d)\le C(a,d)+C(b,c)\text{for }a\le b\le c\le d.$

Cost functions that satisfy it in practice:

• $C(k,j)=$ (sum of a range)${}^2$, or any convex function of a range sum
• $C(k,j)=$ number of inversions / pairs inside $[k,j]$
• $C(k,j)=$ cost of grouping $[k,j]$ into one cluster with a central representative
• $C(k,j)=$ number of distinct values in $[k,j]$

Verify before trusting

Brute-force the $O(n^2)$ DP on small random inputs, record the argmins, and check they are non-decreasing. Thirty seconds of checking beats debugging a wrong answer. See Yao’s theorem for the formal conditions.

Computing $C(k,j)$ efficiently

The recursion assumes $C$ is $O(1)$. When it is not, exploit the fact that consecutive evaluations move $k$ and $j$ by one — maintain the value with a two-pointer / Mo’s-style incremental structure:

int curL, curR; long long curCost;
long long C(int l, int r) {
    while (curR < r) add(++curR);
    while (curL > l) add(--curL);
    while (curR > r) remove(curR--);
    while (curL < l) remove(curL++);
    return curCost;
}

The amortized cost is $O(n\log n)$ total, matching the recursion — this combination is the standard solution to “partition an array into $k$ segments minimising the total number of equal pairs” style problems.

The optimisation family

Recurrence	Requirement	Technique	Time
$dp[i][j]={\min }_{k}dp[i-1][k]+C(k,j)$	monotone opt	D&C DP	$O(kn\log n)$
same, offline, totally monotone	Monge	SMAWK	$O(kn)$
same, online	Monge	LARSCH	$O(kn)$
$dp[l][r]={\min }_{k}dp[l][k]+dp[k][r]+C$	QI + monotone	Knuth	$O(n^2)$
$dp[i]={\min }_{j}dp[j]+b_j{x}_i$	lines	CHT	$O(n)$ / $O(n\log n)$
fixed-width window	none	monotone queue	$O(n)$
”exactly $k$ groups” with convex cost in $k$	convexity	Aliens trick	$O(n\log (\text{range}))$

D&C DP vs Aliens trick

Both attack “partition into exactly $k$ parts”. D&C DP keeps the $k$ dimension and costs $O(kn\log n)$; Aliens trick removes it, costing $O(n\log C)$ times the cost of one unconstrained solve. When $k$ is large (say $k=10^5$), Aliens is the only option. When $k$ is small, D&C DP is simpler and has no convexity requirement on the answer-vs-$k$ curve.

See also: Knuth Optimization · Aliens Trick · SMAWK