Divide and Conquer DP Optimization
Speed up row-by-row transition minimization when the optimal split point moves monotonically.
Divide and Conquer DP Optimization
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Divide and conquer DP optimization is the first optimization I check when a transition looks like ``take the best split point \(k\) for every position \(j\)'' and the straightforward implementation is one quadratic loop too slow.
When to Use It
Use it when the recurrence has the shape \[ dp[i][j] = \min_{k \le j} \bigl(dp[i-1][k-1] + C(k, j)\bigr), \] and the optimal split points satisfy: \[ opt[i][j] \le opt[i][j+1]. \]
That monotonicity usually comes from a quadrangle inequality or a similar structure in the cost function.
Core Idea
If the best split index for \(j\) never moves left when \(j\) increases, then after computing the optimum at the middle position, the left half only needs to search smaller split indices and the right half only needs to search larger ones.
That is exactly the same pruning pattern as divide and conquer on a monotone answer boundary.
Key Insight
The optimization does not come from algebraic magic. It comes from reducing the search interval for the best split at each position. Once the opt indices are monotone, every recursive subproblem can ignore a large part of the \(k\)-range.
Operations / Main Technique
verify or prove opt monotonicity,
compute one DP row from the previous row,
recurse on the left and right halves with narrowed split ranges.
Worked example.
If the middle position \(j = 50\) is optimized by \(k = 18\), then every position left of \(50\) only needs to try split points up to \(18\), while positions to the right only need to try split points from \(18\) onward.
Correctness Intuition
The monotonicity of the optimal split points guarantees that recursion never removes the true optimum from a subproblem's search interval. So every position still checks all of its valid candidates, just within a much smaller window.
Complexity Analysis
For one row of length \(n\), the optimized computation is typically \(O(n \log n)\) if evaluating one candidate is \(O(1)\). Over \(m\) rows, that becomes \(O(m n \log n)\).
Implementation
The reference code is the reusable core: given a previous row, a current row, and a cost function, it fills one row via the divide-and-conquer recursion.
Common Pitfalls
Using the optimization without actually proving opt monotonicity.
Off-by-one mistakes in the split range and in the meaning of \(dp[i-1][k-1]\).
Forgetting that the cost function itself still needs to be \(O(1)\) or cheap enough.
Variants / Extensions
Knuth optimization, which is even stronger but applies to a narrower family of recurrences.
Convex hull trick when the transition can be rewritten as line queries.
Aliens trick when the DP is wrapped inside a parametric search.
Practice Problems
Partition DP with monotone optimal cut positions.
Grouping or clustering DP where the segment cost is precomputable.
Circular Barn and similar row-by-row partition problems.
References
Code
Contest-ready reference implementation for the idea explained above.
template <class Cost>
void compute_dp_row(int left, int right, int opt_left, int opt_right,
const vector<long long>& prev, vector<long long>& cur, Cost cost) {
if (left > right) {
return;
}
int mid = (left + right) / 2;
pair<long long, int> best = {(long long)4e18, -1};
int upper = min(mid, opt_right);
for (int k = opt_left; k <= upper; ++k) {
long long candidate = (k == 0 ? 0 : prev[k - 1]) + cost(k, mid);
if (candidate < best.first) {
best = {candidate, k};
}
}
cur[mid] = best.first;
compute_dp_row(left, mid - 1, opt_left, best.second, prev, cur, cost);
compute_dp_row(mid + 1, right, best.second, opt_right, prev, cur, cost);
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.