Offline Divide and Conquer for DP

Quick Revisit

• USE WHEN: layer-by-layer DP where the optimal split point is monotone: opt(i) ≤ opt(i+1)
• INVARIANT: optimal decision point never decreases as row index increases (monotone minima)
• TIME: O(kn log n) for k layers, n states per layer | SPACE: O(n)
• CLASSIC BUG: off-by-one in search range — opt_hi for left half is best_j, opt_lo for right half is best_j
• PRACTICE: 08-ladder-mixed

When a 1D DP transition satisfies the monotone minima property -- the optimal decision point for row $i$ never decreases as $i$ increases -- you can compute an entire DP layer in $O(n\log n)$ instead of $O(n^2)$ by recursively narrowing the search range.

Difficulty: [Advanced]Prerequisites: DP -- 1D Introduction, Divide and ConquerCF Rating Range: 2000-2400+

---

Not to Be Confused With

This technique goes by many names: "Divide and Conquer DP optimization," "SMAWK-lite," "monotone minima D&C." It is not the same as:

• CDQ Divide and Conquer (CDQ D&C) -- that's for multi-dimensional partial order problems (counting inversions, etc.).
• Knuth's Optimization (Knuth) -- that exploits the quadrangle inequality on interval DP. Offline D&C optimization works on layer-by-layer DP with a simpler monotonicity condition.

A detailed treatment with full proofs lives in DP -- D&C Optimization. The boundary is intentional: that file is the full mathematical treatment (the quadrangle / SMAWK theory, monotonicity proofs, classic DP examples). This file is the short recognition / template reference -- how to slot the technique into your offline toolkit alongside Mo's, CDQ, and parallel binary search. If you are looking for "why does this work?", go to the DP chapter. If you are looking for "is this the right tool, and what does the recursion look like?", you are in the right place.

The Recurrence

You have a DP with $k$ layers (e.g., "partition array into $k$ groups"):

$$dp[t][i]=\underset{j<i}{min}(dp[t-1][j]+C(j+1,i))$$

where $C(l,r)$ is the cost of a segment $[l,r]$. Define $\text{opt}(i)$ = the $j$ that minimizes the expression for a given $i$.

Monotone minima condition: $\text{opt}(i)\le \text{opt}(i+1)$ for all $i$.

This holds when $C$ satisfies the concave (or convex) totally monotone property -- informally, when wider segments are "disproportionately expensive."

The Algorithm

To compute one DP layer (fixing $t$), we need $dp[t][i]$ for all $i\in [0,n)$.

  solve(lo, hi, opt_lo, opt_hi):
      // Compute dp[t][i] for i in [lo, hi]
      // knowing opt(i) is in [opt_lo, opt_hi]

      mid = (lo + hi) / 2
      best_j = argmin over j in [opt_lo, min(mid, opt_hi)]
                   of dp[t-1][j] + C(j+1, mid)
      dp[t][mid] = dp[t-1][best_j] + C(best_j+1, mid)

      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

Each level of recursion scans a total of $O(n)$ candidates (the search ranges partition $[0,n)$). Recursion depth is $O(\log n)$. Total per layer: $O(n\log n)$. Over $k$ layers: $O(kn\log n)$.

Trace

Array $a=[3,1,4,1,5]$, $C(l,r)=(\sum _{i=l}^r{a}_i{)}^2$, computing layer $t=2$:

  solve(0, 4, 0, 4):
    mid=2, scan j=0..2:
      j=0: dp[1][0] + C(1,2) = 0 + 25 = 25
      j=1: dp[1][1] + C(2,2) = 9 + 16 = 25
      j=2: dp[1][2] + C(3,2) = invalid
    best_j=0, dp[2][2]=25

    solve(0, 1, 0, 0):
      mid=0: j=0 only -> dp[2][0]=dp[1][0]+C(1,0)=0
      solve(1, 1, 0, 0):
        mid=1: j=0 -> dp[2][1]=dp[1][0]+C(1,1)=16

    solve(3, 4, 0, 4):
      mid=3: scan j=0..3 -> find best_j
      ...

Implementation

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long dp[2][5001];  // rolling two layers
long long cost(int l, int r);  // problem-specific cost function

void solve(int lo, int hi, int opt_lo, int opt_hi, int cur) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    long long best = 1e18;
    int best_j = opt_lo;
    for (int j = opt_lo; j <= min(mid - 1, opt_hi); j++) {
        long long val = dp[cur ^ 1][j] + cost(j + 1, mid);
        if (val < best) {
            best = val;
            best_j = j;
        }
    }
    dp[cur][mid] = best;
    solve(lo, mid - 1, opt_lo, best_j, cur);
    solve(mid + 1, hi, best_j, opt_hi, cur);
}

int main() {
    // ... read input, compute prefix sums for cost() ...
    // Base layer
    for (int i = 0; i < n; i++) dp[0][i] = cost(0, i);
    for (int t = 1; t < k; t++) {
        fill(dp[t & 1], dp[t & 1] + n, 1e18);
        solve(0, n - 1, 0, n - 1, t & 1);
    }
    cout << dp[(k - 1) & 1][n - 1] << "\n";
}

Recognizing the Pattern

Suspect this optimization when you see:

1. "Partition into exactly $k$ groups, minimize total cost" -- the $k$ layers are your groups.
2. Cost function $C(l,r)$ is "convex-ish" -- wider ranges cost more than the sum of parts (e.g., $(\text{sum}{)}^2$, variance, squared deviation).
3. $n$ up to $5000-{10}^5$ with $k$ up to $n$ -- $O(k{n}^2)$ is too slow, $O(kn\log n)$ fits.

Monotonicity is a required property, not a hope. The technique is correct only if $\text{opt}(i)\le \text{opt}(i+1)$ holds for every $i$, and silently returns wrong answers otherwise. The standard sufficient condition is that the cost function $C$ satisfies the quadrangle / concave totally-monotone inequality; see the DP chapter for the proof template. As a debugging heuristic (not a validity argument), computing $\text{opt}(i)$ for a few values and checking that it is non-decreasing can catch a broken monotonicity assumption early -- but a small-case sanity check is not a proof. If you cannot articulate why $C$ is concave/quadrangle on the problem at hand, do not trust the technique.

Pitfalls

• Off-by-one in opt_hi bound. The scan range for $j$ must not exceed $mid-1$ (you can't transition from yourself).
• Forgetting to handle empty ranges. lo > hi should return immediately.
• Cost function must be efficient. If cost(l, r) is $O(n)$, the total is $O(k{n}^2\log n)$ -- worse than brute force. Precompute prefix sums.
• Not verifying monotonicity. If $\text{opt}(i)$ is not monotone, this technique gives wrong answers silently.

Practice Problems

#	Problem	Difficulty	Notes
1	CF 868F -- Yet Another Minimization Problem	2500	Partition into $k$ groups, cost = pairs of equal elements
2	CF 321E -- Ciel and Gondola	2000	Classic D&C DP optimization
3	APIO 2014 -- Sequence	--	Partition with product-based cost
4	CF 833B -- The Bakery	2200	Partition array into $k$ segments, maximize distinct elements

Further Reading

• DP -- D&C Optimization -- full treatment with proofs and more examples
• CDQ Divide and Conquer -- the other "D&C" offline technique (different purpose)
• Knuth's Optimization -- a related but distinct optimization for interval DP

---