Divide and Conquer DP

Divide and Conquer DP is a dynamic programming optimization (not the same thing as plain divide-and-conquer algorithms).

This lesson follows CP-Algorithms — Divide and Conquer DP.

The recurrence

Many DP problems look like:

dp(i, j) = min_{0 ≤ k ≤ j}  dp(i−1, k−1) + C(k, j)

with dp(i, j) = 0 when j < 0. Here C(k, j) is a segment cost.

Take 0 ≤ i < m and 0 ≤ j < n, and assume C evaluates in O(1). Brute force is O(m n²): m·n states, up to n choices of k each.

Monotonicity of opt

Let opt(i, j) be a minimizing k for that state. If the cost satisfies the quadrangle inequality (QI)

C(a, c) + C(b, d) ≤ C(a, d) + C(b, c)   for all a ≤ b ≤ c ≤ d

then typically

opt(i, j) ≤ opt(i, j + 1)

— the optimal split point is non-decreasing in j for fixed i.

So once you know opt(i, mid), every j < mid only needs k ≤ opt(i, mid), and every j > mid only needs k ≥ opt(i, mid).

Divide-and-conquer evaluation

For a fixed layer i:

Compute opt at the middle index mid = ⌊(L+R)/2⌋ by scanning k in the current bounds [optl, optr].
Recurse on the left half with upper bound opt.
Recurse on the right half with lower bound opt.

There are O(log n) recursion levels. Across one level the total length of all k-intervals is O(n), so one layer is O(n log n) and the full DP is O(m n log n).

Sketch of the level-size bound: if S_k is total opt-interval length at level k, splitting at most 2^k intervals gives S_{k+1} ≤ S_k + 2^k. With S_0 = n you get S_k ∈ O(n).

Generic template

compute fills one row dp_cur from the previous row dp_before. Call compute(0, n-1, 0, n-1).

int m, n;
vector<long long> dp_before, dp_cur;

long long C(int i, int j);

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

long long solve() {
    dp_before.assign(n, 0);
    dp_cur.assign(n, 0);

    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i);

    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1);
        dp_before = dp_cur;
    }

    return dp_before[n - 1];
}

🧪 Tiny instance: C(k,j)=(j−k+1)², m=3, n=8

Check: recurrence & complexity

Quiz