Divide and Conquer Optimization for DP
Divide and conquer DP optimization speeds up a row of transitions when its optimal split points move monotonically. It replaces a full search over every possible split at every endpoint with recursive searches over narrower candidate ranges. The difficult part is not writing the recursion: it is proving that an optimal split cannot move backwards.
We will partition a nonnegative array into exactly k nonempty contiguous groups, minimizing the sum of squared group sums. Prefix sums make one transition constant-time; monotone split positions then reduce O(kn²) time to O(kn log n). This is a concrete example with a proof, not a template that can safely be applied to every quadratic DP.
Prerequisites: Introduction to Dynamic Programming, Prefix Sums, layered partition DP, and basic recursion. Use two DP rows so all transitions in one layer read the previous layer. Difficulty: Expert.
Build the idea
Define a state and a valid final group
Let P[i]=a₁+⋯+aᵢ, with P[0]=0. Let D[g][i] be the minimum cost for the first i elements in exactly g groups. A split after position j leaves elements j+1 through i as the last group. Its sum is P[i]−P[j], so define W(j,i)=(P[i]−P[j])².
D[g][i] = min over g−1≤j<i of {D[g−1][j]+W(j,i)}. The boundary j≥g−1 leaves enough elements for the previous groups; j<i makes the last group nonempty. Start with D[0][0]=0 and every other zero-group state impossible (INF). There are O(kn) states and up to O(n) candidates per state, giving the O(kn²) baseline.
State the required monotonicity precisely
For one fixed row g, let opt[i] be the leftmost split j attaining the minimum. The optimization requires opt[i]≤opt[i+1] for every pair of consecutive valid endpoints in that row. It does not require the array values or DP values themselves to be increasing.
If opt[mid]=b, every smaller endpoint has a leftmost optimum at most b, and every larger endpoint has one at least b. These are the bounds the recursion will use. Guessing them from a few examples is not a correctness argument; establish this property for the actual recurrence and tie convention before restricting the candidates.
Prove the property for squared nonnegative group sums
For prefix boundaries a≤b≤c≤d, write X=P[b]−P[a], Y=P[c]−P[b], and Z=P[d]−P[c]. Because every input value is nonnegative, X and Z are nonnegative. Expanding the four squares gives W(a,d)+W(b,c)−W(a,c)−W(b,d)=2XZ≥0. Equivalently, W(a,c)+W(b,d)≤W(a,d)+W(b,c). This is the Monge, or quadrangle, inequality for this cost.
Now add the previous-row term to obtain A(j,i)=D[g−1][j]+W(j,i). Each previous-row term appears once on each side, so the inequality remains true. Suppose two endpoints c<d had crossed optima: b=opt[c]>a=opt[d]. Optimality favors b at c and a at d; the Monge inequality favors the uncrossed pair a at c and b at d. Combining the inequalities forces a tie at c, so a is also optimal there. Since a<b, this contradicts choosing b as the leftmost optimum. Therefore opt cannot decrease.
Compute the middle endpoint and recurse
compute(left,right,firstSplit,lastSplit) computes endpoints left..right whose leftmost optimal splits lie within firstSplit..lastSplit. First choose middle=⌊(left+right)/2⌋ and scan firstSplit through min(middle−1,lastSplit). Skip previous-row INF states. Keep the first candidate on ties by updating only when candidate<bestCost.
After finding bestSplit, recurse on endpoints left..middle−1 with candidate bounds firstSplit..bestSplit, and on middle+1..right with bounds bestSplit..lastSplit. The boundary bestSplit belongs to both searches because several endpoints may have the same optimum. Stop when left>right. For row g, start with endpoints g..n and candidate splits g−1..n−1. All those states are feasible when 1≤g≤k≤n.
Worked example: fill the two-group row
Take a=[1,2,3,4] and k=2. Prefix sums are [0,1,3,6,10]. One group has no choice of partition: D[1][i]=P[i]². For two groups, evaluate all valid final splits to understand the result before optimizing it.
Endpoint i D[1][i] D[2][i] Leftmost opt[i] 1 1 Impossible — 2 9 5 1 3 36 18 2 4 100 52 3 For endpoint 4, split j=1 gives 1²+9²=82, j=2 gives 3²+7²=58, and j=3 gives 6²+4²=52. Thus the optimal groups are [1,2,3] and [4]. The two-group opt sequence is 1,2,3, which agrees with the proof.
The optimized call compute(2,4,1,3) first handles middle=3. Splits 1 and 2 give 26 and 18, so bestSplit=2. The left recursive call computes endpoint 2 using candidate bounds 1..2, clipped to just 1. The right call computes endpoint 4 using only splits 2..3; it can skip split 1. Larger rows repeat this narrowing at every recursion level.
Keep layers separate and arithmetic safe
previous[j] stores D[g−1][j], while current[i] receives D[g][i]. Never update previous while computing a row: that would read partially updated states and change the recurrence. Reset current to INF, compute all valid endpoints, then swap the vectors. Values at impossible endpoints remain INF, and the next row skips them.
The input contract is 1≤k≤n≤5000 and 0≤aᵢ≤10000. Hence P[n]≤50,000,000 and any feasible sum of squared group sums is at most P[n]²≤2.5×10¹⁵. long long safely stores both a square and the candidate total under these bounds, while int is sufficient for indices. INF is larger than every valid answer, and INF is checked before addition. For larger inputs, prove a new numeric bound rather than reusing this one.
Know when the optimization is invalid
For signed input a=[−2,1,−1,−2], the leftmost two-group optima for endpoints 2,3,4 are 1,2,1. The optimum moves backwards, so the recursive right-side restriction can discard the correct split. This example is deliberately outside the program’s nonnegative-input contract.
A different cost, extra transition restrictions, or a recurrence that reads the current row also needs a new proof. If cost evaluation is not O(1), include its expense in the final complexity. Knuth optimization has a different interval recurrence and different bounds; a line-based Convex Hull Trick optimization uses different structure again. When monotonicity is unproved or false, keep the unrestricted baseline or choose an applicable alternative.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
#include<functional>
#include<limits>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int length,groupCount;
if(!(cin>>length>>groupCount)){
return 0;
}
vector<long long>prefix(length+1,0);
for(int index=1;index<=length;index++){
long long value;
cin>>value;
prefix[index]=prefix[index-1]+value;
}
const long long INF=numeric_limits<long long>::max()/4;
vector<long long>previous(length+1,INF);
vector<long long>current(length+1,INF);
previous[0]=0; // Zero elements can form zero groups at zero cost.
for(int group=1;group<=groupCount;group++){
fill(current.begin(),current.end(),INF);
// Endpoints are in [left,right]; their optimal splits are in [firstSplit,lastSplit].
function<void(int,int,int,int)>compute=[&](int left,int right,int firstSplit,int lastSplit){
if(left>right){
return;
}
int middle=left+(right-left)/2;
int bestSplit=-1;
long long bestCost=INF;
for(int split=firstSplit;split<=min(middle-1,lastSplit);split++){
if(previous[split]==INF){
continue; // An impossible prefix cannot supply a transition.
}
long long groupSum=prefix[middle]-prefix[split];
long long candidate=previous[split]+groupSum*groupSum;
if(candidate<bestCost){
bestCost=candidate;
bestSplit=split; // Strict improvement keeps the leftmost tie.
}
}
current[middle]=bestCost;
// Monotone optima justify both restrictions, including bestSplit in each range.
compute(left,middle-1,firstSplit,bestSplit);
compute(middle+1,right,bestSplit,lastSplit);
};
compute(group,length,group-1,length-1);
previous.swap(current); // Finish the entire row before reusing its storage.
}
cout<<previous[length]<<'\n';
}
Complexity analysis
The baseline costs O(kn²) time. For the optimized program, one row has O(log n) recursion levels. At each level, the candidate ranges overlap only at shared best-split boundaries: their total scan length is O(n), including the O(n) possible boundary/state overhead. Thus a row takes O(n log n), and k rows take O(kn log n). This bound relies on O(1) prefix-sum cost evaluation and proven monotone optima; divide and conquer alone does not guarantee it.
Prefix sums and two DP rows use O(n) space. Balanced endpoint recursion has O(log n) depth, so total auxiliary space stays O(n). This implementation prints the optimal value only. Reconstructing every chosen split across all k rows would require additional storage or a separate reconstruction strategy.
- Do not assume monotonicity just because the DP has a minimum over j. Prove it for the precise cost and feasible split ranges.
- Signed values break this example’s proof; zeros are allowed and make consistent leftmost tie handling important.
- Keep split<endpoint and split≥group−1 so every group is nonempty.
- Write a separate current row, then swap. Reset impossible states instead of keeping stale values.
- Pass bestSplit to both recursive candidate ranges. Using bestSplit−1 or bestSplit+1 can discard repeated optima.
- Check INF before arithmetic and bound intermediate squares, not only the final printed answer. The code assumes valid input satisfying its stated limits.
Example input and output
Read n k with 1≤k≤n≤5000, then n nonnegative integers ≤10000. Partition into exactly k nonempty contiguous groups and print the minimum sum of squared group sums.
Input
4 2 1 2 3 4
Output
52
For one group, the row is [1,9,36,100] at endpoints 1..4. For two groups, valid endpoints 2..4 have values [5,18,52]. The final value 52 comes from the split after element 3, whose group sums are 6 and 4. The worked example above shows how the midpoint recursion finds the same row.
Practical applications
Use this optimization for layered partition DPs with inexpensive transition costs and a proof of monotone optimal split positions, often through a Monge inequality. Start with a correct slow recurrence and compare it against the optimized version on small random inputs. That comparison catches implementation errors; it cannot prove a new mathematical assumption.
Related lessons: Prefix Sums explains constant-time group sums; Divide and Conquer DP Optimization provides further partition-DP context; Convex Hull Trick handles transitions expressible as line queries. The squared-sum cost can also be expanded into lines, but that is a separate optimization with its own ordering conditions.
Check your understanding
What justifies restricting recursive split ranges?
Put it into practice
Practice: implement the O(kn²) baseline and compare every valid state against the optimized version for small arrays. Include k=1, k=n, all-zero arrays, repeated values, and the [1,2,3,4] worked example. Separately compute unrestricted optima for [−2,1,−1,−2] to demonstrate why signed inputs are excluded.
Show a hint
In the baseline, enumerate split from group−1 through endpoint−1 and read only the previous row. Scan in increasing order and update on strict improvement to match the optimized leftmost tie rule.