↩ back to Dynamic Programming

Divide and Conquer DP Optimization

A large share of this site's Dynamic Programming entries share one transition shape: dp[i] = min over j < i of (dp_prev[j] + cost(j, i)) — the best way to reach position i is the best way to reach some earlier position j, plus whatever it costs to go from j to i directly. Computed the obvious way, filling in n positions each by scanning every earlier j, that's O(n²) total for one pass over the array. This page's trick cuts that to O(n log n) whenever one extra property holds: the best j for position i, call it opt(i), never moves backward as i grows. That single guarantee — not an assumption, a property of cost that has to actually be checked, the same way a binary search's caller has to actually sort first — lets a divide-and-conquer recursion find every opt(i) while shrinking the window of candidates it has to try at each step, instead of rescanning from scratch every time.

This is a different kind of speedup from Convex Hull Trick, this site's other DP-transition speedup, even though competitive programmers often reach for either on the same problem. CHT needs cost(j, i) rewritten as a family of literal linear functions of j, evaluated at a point that depends on i — a real algebraic rewrite that isn't always obvious, or even possible. This trick only needs the weaker, usually easier-to-check fact that opt(i) is monotonic; it never needs cost expressed as m·x + b at all. The worked example below happens to admit both approaches (most textbook examples do, which is exactly why CHT and this page's technique are so often taught side by side), but the monotonicity property this page relies on is the more general of the two — it's also what makes Longest Increasing Subsequence's binary search and the range-split questions in this site's own DP funnel work, even though neither of those pages needed to find a linear rewrite either.

The concrete problem below: a dispatcher has n days of forecast parcel volume and wants to split the week into exactly two contiguous shift blocks, minimizing a quadratic overtime penalty — (sum of a block)² — that punishes loading one block too heavily far more than it punishes a few extra light days. dp1[j], the cost of the first block alone if it ends at day j, has a closed form (just the square of day 1..j's total volume) and needs no search at all. dp2[i] = min over j < i of (dp1[j] + cost(j, i)) is the real question: given the first block already ends somewhere, where should the second one end, for every possible ending day i? Applying this exact transition K − 1 times in a row — dp3 from dp2, dp4 from dp3, and so on — is how a general "split into exactly K contiguous groups" dynamic program gets the same speedup at every layer, turning O(K·n²) into O(K·n log n) overall. This page, like Convex Hull Trick's own page, shows a single layer transition in full; chaining K of them is the same code called K − 1 times.

Try it

Twelve days of forecast parcel volume: [7, 4, 9, 2, 6, 8, 3, 5, 1, 9, 4, 6] hundred parcels. dp1[] (bottom row) is already filled in — the trivial one-block cost, a squared running total. Press Step or Run to watch the divide-and-conquer recursion fill in dp2[] (top row) — not left to right, but middle-out: it solves the midpoint of a range first, then narrows the candidate window before recursing on each half. Watch the candidate window (highlighted in the dp1 row) shrink as the recursion goes deeper, and the running tally of split points actually checked against what a plain left-to-right scan would have needed.

Why it works

Suppose, for two positions i₁ < i₂, the truly best predecessors somehow came out backward — opt(i₁) larger than opt(i₂). Swap them: use opt(i₂) for i₁ and opt(i₁) for i₂ instead. For any cost function where splitting a larger total into two more balanced pieces is never worse than splitting it into two more lopsided ones — the quadrangle inequality, cost(a,d) + cost(b,c) ≥ cost(a,c) + cost(b,d) for a ≤ b ≤ c ≤ d, which a squared-sum penalty satisfies directly — that swap can only help or tie, never hurt. So an optimal assignment can always be rearranged into one where opt is non-decreasing, and once that's true, the recursion below can safely narrow its own search window without ever discarding the real answer.

solve(lo, hi, optLo, optHi) computes dp2[mid] for mid = ⌊(lo+hi)/2⌋ by scanning only candidates in [optLo, min(mid-1, optHi)] — never the full [1, mid-1] a plain scan would need. Whatever candidate wins there, bestJ, becomes the new upper bound for the left half's own search (nothing left of mid can ever need a later predecessor than mid itself did, since opt only moves forward) and the new lower bound for the right half's. Each level of the recursion partitions [lo, hi] into disjoint ranges whose candidate windows, laid end to end, never exceed the full n — so each level costs O(n) total work, and there are O(log n) levels, for O(n log n) altogether. On the twelve-day demo above, the very first call already shows the shrink directly: solving dp2[7] first scans all 6 candidates in [1, 6] and finds bestJ = 3; every call on the left half afterward is confined to [1, 3], every call on the right half to [3, 11] — neither ever has to look at the full range again.

Reference implementation

// dp1 must already be fully computed for every index before this runs --
// the recursion visits mid-points out of left-to-right order, so nothing
// here can be filled in lazily as a rolling single-pass sweep would.
function divideAndConquerDP(dp1, cost, n) {
  const dp2 = new Array(n + 1).fill(Infinity);
  let candidateChecks = 0;

  function solve(lo, hi, optLo, optHi) {
    if (lo > hi) return;
    const mid = (lo + hi) >> 1;
    let best = Infinity, bestJ = -1;
    // scanHi caps at mid - 1: j must stay strictly before mid, or this
    // isn't a valid split at all -- see Pitfalls for what skipping the cap breaks.
    const scanHi = Math.min(mid - 1, optHi);
    for (let j = optLo; j <= scanHi; j++) {
      candidateChecks++;
      const v = dp1[j] + cost(j, mid);
      if (v < best) { best = v; bestJ = j; }
    }
    dp2[mid] = best;
    solve(lo, mid - 1, optLo, bestJ);
    solve(mid + 1, hi, bestJ, optHi);
  }

  solve(2, n, 1, n - 1);
  return { dp2, candidateChecks };
}

Pitfalls

The monotonicity has to actually hold — it doesn't come free just because the recursion runs and returns an answer. Feed the same code an arbitrary cost table with no quadrangle inequality anywhere in it, and nothing crashes; it just silently narrows away the real optimum. A concrete five-day counterexample makes this exact: with a cost table whose true optimal predecessor sequence is opt(2..5) = [1, 2, 1, 1] — note the drop back from 2 to 1, a real monotonicity violation — the correct answer for day 4 uses predecessor 1 at cost 9, but the recursion, having already narrowed its window to optLo = 2 while solving day 3, never looks at predecessor 1 again and reports 13 instead — wrong, with no error anywhere. Generalized into a stress test: 20,000 random, structurally arbitrary cost tables (no reason to satisfy the inequality, deliberately) against an independent brute-force baseline came back wrong on 17,263 of them — 86.3%. There's no cheap defensive check worth adding inside solve() for this, the same way Convex Hull Trick's own insertion order can't be verified without paying the full cost the structure exists to avoid — the property has to be confirmed about cost itself, analytically, before reaching for this trick at all.

min(mid - 1, optHi) is a correctness requirement, not just a tightening for speed. Dropping the mid - 1 cap and scanning all the way to optHi lets j = mid (or later) sneak into the candidate pool — a "split" where the second block starts and ends at the same day, which is not a valid predecessor at all. On the demo's own increasing-prefix-sum dp1, this bug happens not to flip any answer, since dp1 only ever grows and a same-day split can't beat a real one — an easy way to ship it unnoticed. Testing the identical uncapped code against 5,000 random trials where dp1 isn't forced to be increasing (the general case this trick has to work for, not just this page's one convenient dataset) came back wrong on all 5,000. A correctness bound that happens not to bite on one dataset is still a bug, confirmed here by changing the dataset rather than assumed safe because the demo kept working.

Complexity

Time: O(n log n) for one full layer, against O(n²) for the plain scan it replaces — confirmed directly at increasing scale, not just asserted: on the twelve-day demo, 41 candidate checks fill the whole dp2[] array against 66 a left-to-right scan would need (38% fewer, with only twelve positions to amortize over). At n = 1,000, 9,970 checks against 499,500 — 2.0% as many. At n = 20,000, 293,520 against 199,990,000 — 0.15% as many, and within 3% of n·log₂n ≈ 285,754, the shape the asymptotic bound predicts. Chaining K layers (the general "split into exactly K groups" problem named above) multiplies both sides by K, turning O(K·n²) into O(K·n log n). Space: O(n) for the current and previous layer's arrays — both have to be fully materialized before a layer's recursion starts, since solve() visits midpoints out of left-to-right order and can't be computed as a single rolling array the way some one-dimensional entries on this site are.

This site's guide, Choosing a Dynamic Programming Approach, sets this entry aside up front, the same way Choosing a Convex Hull Algorithm sets aside Convex Hull Trick: it isn't a thirteenth subproblem shape competing with the other twelve, it's a speedup technique that bolts onto several of them once their own cost function's optimal split point is checked to be monotonic.