Divide and Conquer DP Optimization

Divide-and-conquer optimization reduces a suitable row of partition DP by bounding its optimal split indices. We reuse nonnegative squared-block-sum partitioning from the direct lesson. The improvement is not universally valid for every partition cost:we establish a Monge inequality and invoke its monotone-argmin consequence. The implementation keeps only two group rows and outputs the optimum value.

Prerequisites: Partition DP; Prefix Sums; divide and conquer; Monge inequality.

Build the idea

1. Recognize the repeated subproblems

   The direct recurrence has K·n states and up to n preceding boundaries each, for O(Kn²) time. If the smallest minimizing boundary opt[g][i] never moves left as i grows, knowing a middle state’s best split bounds all states to its left/right. This is information about the optimization landscape, not merely about nondecreasing numeric DP values.

2. Define the state

   D[g][i] is minimum cost to partition prefix i into exactly g nonempty blocks; S is the prefix sum. Block cost W(j, i)=(S[i]−S[j])². previous[j] stores row g−1 and current[i] the row under construction. The optimization only restricts which j values need testing; it does not change the definition of D or allow empty groups.

3. Derive the transition

   To compute endpoints [left, right] with allowed split range [optLeft, optRight], evaluate the middle endpoint by scanning legal j≤mid−1. Retain its smallest minimizing split best. Recurse left with upper split bound best, and right with lower bound best. This uses only previous-row values, so endpoints within the current row need not be processed sequentially.

   $$\mathrm{opt}\left[g\right]\left[i\right]\le \mathrm{opt}\left[g\right][i+1]$$

4. Base cases and computation order

   Base previous[0]=0 and other zero-group states INF. For each g, reset current to INF and compute endpoints g…n with initial splits g−1…n−1. Increasing group count guarantees the previous row exists. Skip INF predecessors and use ascending j with strict improvement to choose the smallest minimizer consistently. The legal nonempty ranges ensure a finite best split exists.

5. Correctness and invariant

   For a≤b≤c≤d, let X=S[b]−S[a]≥0 and Z=S[d]−S[c]≥0. Then W(a, d)+W(b, c)−W(a, c)−W(b, d)=2XZ≥0. This Monge/quadrangle inequality yields nondecreasing smallest argmins after adding the previous-row term, which cancels between compared splits. To see argmin monotonicity, suppose a later endpoint preferred a smaller split b<a. The Monge comparison and the two optimality inequalities force equality, so b would also minimize the earlier endpoint, contradicting its smallest minimizer a. Thus recursive bounds preserve the optimum. With negative entries, the sign proof can fail.

6. Work the example

   Array [1,2,3,4], K=2 has previous one-group row [INF,1,9,36,100] with only valid positive endpoints used. Two-group values at endpoints 2,3,4 are 5,18,52, with smallest best splits 1,2,3. Their increasing indices illustrate the property; the inequality, not this single table, is the proof. The output 52 matches direct partition DP.

   endpoint i	2	3	4
   D[2][i]	5	18	52
   smallest split	1	2	3

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
const long long INF=4000000000000000000LL;
std::vector<long long>prefix,previous,current;
void compute(int left,int right,int optLeft,int optRight){
    if(left>right){
        return;
    }
    int mid=(left+right)/2,best=-1;
    current[mid]=INF;
    for(int j=optLeft;j<=std::min(optRight,mid-1);++j){
        if(previous[j]!=INF){
            long long sum=prefix[mid]-prefix[j],value=previous[j]+sum*sum;
            if(value<current[mid]){
                current[mid]=value;
                best=j;
            }
        }
    }
    compute(left,mid-1,optLeft,best);
    compute(mid+1,right,best,
        optRight); // Monotone smallest minimizing split bounds each recursive search.
}
int main(){
    int n,K;
    std::cin>>n>>K;
    prefix.resize(n+1);
    for(int i=1;i<=n;++i){
        long long a;
        std::cin>>a;
        prefix[i]=prefix[i-1]+a;
    }
    previous.assign(n+1,INF);
    previous[0]=0;
    current.resize(n+1);
    for(int g=1;g<=K;++g){
        std::fill(current.begin(),current.end(),INF);
        compute(g,n,g-1,n-1);
        previous.swap(current);
    }
    std::cout<<previous[n]<<'\n';
}

Complexity analysis

O(Kn log(n+1)) time under O(1) block costs and proven monotone argmins:at each recursion depth, the total scanned split ranges are O(n), with O(log n) depths. O(n) row/prefix storage and O(log n) recursive stack. Compare direct O(Kn²). Costs≤(sum a)²≤4·10^12 fit long long.

Example input and output

Read n K (1≤K≤min(n,100), n≤2000), then n integers in 0..1000. Minimize squared sums of exactly K nonempty contiguous blocks. Print optimum value only.

Input

4 2
1 2 3 4

Output

52

Array [1,2,3,4], K=2 has previous one-group row [INF,1,9,36,100] with only valid positive endpoints used. Two-group values at endpoints 2,3,4 are 5,18,52, with smallest best splits 1,2,3. Their increasing indices illustrate the property; the inequality, not this single table, is the proof. The output 52 matches direct partition DP.

Practical applications

Use for layered prefix-partition recurrences with monotone transition argmins and fast cost queries. Knuth concerns a different interval recurrence and two-sided neighboring bounds. If the cost lacks the required structure, use direct DP or another justified optimization.

Check your understanding

What property lets the left recursive half restrict its split upper bound?

Put it into practice

Compare the optimized row and split choices with direct DP on nonnegative arrays.