the divide-and-conquer DP optimization
Some DPs have a transition of the form dp[i][j] = min over k < j of dp[i-1][k] + cost(k, j): to compute layer i at position j, you search over a split point k. Done naively, finding the best k for each (i, j) scans all candidates, costing O(n) per entry and O(k_layers times n^2) overall. The divide-and-conquer DP optimization is a speed-up that applies when the best split point is monotone — as j increases, the optimal k never moves backward — and it shaves a factor of n down to a factor of log n on the inner search.
Let opt(j) be the best split point k for column j (in a fixed layer). The property you need is monotonicity: opt(j) is non-decreasing in j. When that holds, you compute the layer with a divide-and-conquer recursion. To fill a block of columns [lo, hi] knowing that their optimal k lies in [optL, optR], pick the middle column mid, find its best k by scanning only the range [optL, optR], record opt(mid). Then recurse on the left half [lo, mid-1] with candidate range [optL, opt(mid)] and the right half [mid+1, hi] with [opt(mid), optR]. Because the optimum is monotone, the left columns cannot need a k bigger than opt(mid) and the right columns cannot need one smaller, so you legally shrink the search. Each level of the recursion does O(n) total scanning work across all the mid-columns, and there are O(log n) levels, so one layer costs O(n log n) instead of O(n^2).
With layers (the i index) the total becomes O(k_layers times n log n). This is one of the standard DP speed-up tools alongside the convex-hull trick and Knuth's optimization. The crucial honesty: it is only correct when opt(j) really is monotone, and that monotonicity is itself a property you must verify, not assume. A common sufficient condition is that cost satisfies the quadrangle inequality (the same condition behind Knuth's optimization). If opt(j) is not monotone, the recursion will silently miss the true optimum for some columns — it does not error out, it just returns wrong answers — so prove monotonicity (or at least test it hard) before trusting it.
Partition an array into k contiguous groups minimizing a sum of group costs. The layer recurrence dp[i][j] = min over m of dp[i-1][m] + cost(m+1, j) has a monotone optimal split when cost is well-behaved. Computing each layer by the divide-and-conquer recursion costs O(n log n), so all k layers cost O(k n log n) versus the naive O(k n^2).
Monotone optimal split lets the middle column's choice bound the halves' searches.
This optimization is valid only when the optimal split point is monotone in j (often guaranteed by the quadrangle inequality). Apply it without that property and it returns wrong answers silently — it never crashes, so verify monotonicity first.