1. The $K$-Partition Recurrence & Decision Monotonicity
Many partitioning and clustering problems (such as $k$-medians on a line, partitioning an array into $K$ subarrays to minimize sum of squared sums, or Optimal Batching) have the layered recurrence for $k = 1 \dots K$ and $i = 1 \dots N$:
$$dp[k][i] = \min_{0 \le j < i} \big(dp[k-1][j] + C(j, i)\big)$$Evaluating all pairs $(j, i)$ for each layer $k$ takes $O(K \cdot N^2)$ time. Let $\text{opt}[k][i]$ be the smallest index $j$ that minimizes $dp[k-1][j] + C(j, i)$.
Core Invariant — The Quadrangle Inequality (Monge Property) & Monotonicity of opt
A 2D cost function $C(j, i)$ satisfies the Quadrangle Inequality (Inverse Monge Property for Minimization) if for all $a \le b \le c \le d$:
$$C(a, c) + C(b, d) \le C(a, d) + C(b, c)$$Intuitively: "Two nested intervals $(a, d)$ and $(b, c)$ cost MORE than two crossing/disjoint intervals $(a, c)$ and $(b, d)$" (the marginal penalty of extending an interval grows as the interval gets longer—convexity!).
Theorem: If $C(j, i)$ satisfies the Quadrangle Inequality, then for every fixed layer $k$, the optimal transition decision is monotonically non-decreasing:
2. The Divide-and-Conquer Recursion ($O(K N^2) \to O(K N \log N)$)
To compute a single layer dp_cur[l..r] given that we already know $\text{opt}[i] \in [\text{opt}_L, \text{opt}_R]$ for all $i \in [l, r]$:
- Pick the midpoint $\text{mid} = \lfloor (l + r) / 2 \rfloor$.
- Scan $j \in [\text{opt}_L, \min(\text{mid} - 1, \text{opt}_R)]$ linearly to find $\text{best\_j} = \text{opt}[\text{mid}]$ and set
dp_cur[mid]. - By monotonicity, every $i < \text{mid}$ has $\text{opt}[i] \in [\text{opt}_L, \text{best\_j}]$, and every $i > \text{mid}$ has $\text{opt}[i] \in [\text{best\_j}, \text{opt}_R]$.
- Recurse on
[l, mid - 1]with search range[opt_L, best_j]and on[mid + 1, r]with[best_j, opt_R]!
Why does each layer take $O(N \log N)$ time? Because at each depth of the recursion tree (depth $\le \lceil \log_2 N \rceil$), the decision intervals $[\text{opt}_L, \text{opt}_R]$ are disjoint except at their shared boundary endpoints $\text{best\_j}$, so their lengths sum to at most $N + 2^d = O(N)$ per depth!
Find best_j = opt[mid] in O(optR - optL)"] --> Left["Left Half: i in [l, mid-1]
Search j ONLY in [optL, best_j]"] Root --> Right["Right Half: i in [mid+1, r]
Search j ONLY in [best_j, optR]"]
Hardware Reality — Mo's-Style Sliding Pointers When $C(j, i)$ Cannot Be Computed in $O(1)$
What if $C(j, i)$ is the number of inversions or number of pairs of equal elements inside subarray $A[j..i-1]$, which has no $O(1)$ prefix-sum formula? Because the D&C recursion moves the endpoints $(j, \text{mid})$ across ranges of total length $O(N \log N)$ per layer, you can maintain a single global sliding window $[L_{ptr}, R_{ptr}]$ that increments/decrements one element at a time in $O(1)$, computing $C(j, \text{mid})$ in $O(K N \log N)$ total pointer steps without any Segment Tree!
3. Complexity Matrix
Inspect how Quadrangle Inequality C(a,c)+C(b,d) ≤ C(a,d)+C(b,c) forces decision monotonicity opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j], collapsing O(N³) transitions.
Invariant & State
| $K$-Layer Partition DP Method | Requirement on $C(j, i)$ | Single-Layer Time | Total Time ($K$ Layers) | Auxiliary Space |
|---|---|---|---|---|
| Naive $K$-Partition DP | Arbitrary $C(j, i)$ | O(N^2) | O(K * N^2) | O(N) (Rolling) |
| Divide-and-Conquer DP | Quadrangle Inequality ($ ext{opt}[i] le ext{opt}[i+1]$) | O(N log N) | O(K * N log N) | O(N) |
| SMAWK / Monge Matrix Search | Quadrangle Inequality + $O(1)$ random access $C(j, i)$ | O(N) | O(K * N) | O(N) |
4. Reference C++20 Implementation
#include <algorithm>
#include <cstdint>
#include <vector>
// Partition array a of length N into K non-empty subarrays to minimize sum of (subarray_sum)^2
// C(j, i) = (pref[i] - pref[j])^2 satisfies Quadrangle Inequality: C(a,c) + C(b,d) <= C(a,d) + C(b,c)
long long partition_min_sum_of_squares_dnc(const std::vector<long long>& a, int k_parts) {
const int n = static_cast<int>(a.size());
constexpr long long INF = 1LL << 60;
std::vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i];
auto cost = [&](int j, int i) -> long long {
long long diff = pref[i] - pref[j];
return diff * diff;
};
std::vector<long long> dp_prev(n + 1, INF), dp_cur(n + 1, INF);
dp_prev[0] = 0;
auto compute = [&](auto& self, int l, int r, int opt_l, int opt_r) -> void {
if (l > r) return;
int mid = l + (r - l) / 2;
long long best_val = INF;
int best_j = opt_l;
int upper_j = std::min(mid - 1, opt_r);
for (int j = opt_l; j <= upper_j; ++j) {
if (dp_prev[j] == INF) continue;
long long val = dp_prev[j] + cost(j, mid);
if (val < best_val) {
best_val = val;
best_j = j;
}
}
dp_cur[mid] = best_val;
self(self, l, mid - 1, opt_l, best_j);
self(self, mid + 1, r, best_j, opt_r);
};
for (int k = 1; k <= k_parts; ++k) {
std::fill(dp_cur.begin(), dp_cur.end(), INF);
compute(compute, k, n, k - 1, n - 1);
std::swap(dp_prev, dp_cur);
}
return dp_prev[n];
}Production Pitfall — Applying D&C DP to 1D Self-Dependent Recurrences (dp[i] Depends on dp[j])
Notice that in D&C DP, evaluating dp_cur[mid] happens before dp_cur[l..mid-1] has been computed! Therefore, standard D&C DP requires a 2-layer recurrence where dp_cur[i] depends only on the already-completed previous layer dp_prev[j]. If your recurrence is 1D self-dependent ($dp[i] = \min_{j < i} (dp[j] + C(j, i))$), you cannot evaluate mid before [l, mid-1]—instead, use CDQ Divide-and-Conquer or a Monotonic Decision Hull / Queue!