Partition Dynamic Programming

Partition DP divides a sequence into an exact number of nonempty contiguous groups. We minimize the sum of squared group sums, a cost that rewards balanced totals under nonnegative input. Prefix sums make each block cost constant-time; the DP tries the last boundary. This direct formulation becomes the reference for the later divide-and-conquer optimization.

Prerequisites: Prefix Sums; Interval DP; reconstruction. Related existing lessons: Prefix Sums.

Build the idea

1. Recognize the repeated subproblems

   Choosing K−1 boundaries among n−1 positions is combinatorial. Many choices lead to the same processed prefix and group count. When n≤300, an O(Kn²) transition scan is feasible and far simpler than guessing greedy cuts. The last block’s cost depends on its endpoints through a prefix sum, not on earlier block internals.

2. Define the state

   dp[g][i] is minimum cost to partition the first i entries into exactly g nonempty groups. Prefix S[i] is the sum of entries 1…i. A last group (j, i] has cost (S[i]−S[j])². g and i are both necessary:the same prefix can have different optima for different required group counts.

3. Derive the transition

   Try j from g−1 to i−1. The first j entries must form g−1 groups, and the last nonempty block contributes its squared sum. Minimize dp[g−1][j]+cost(j, i), ignoring unreachable predecessors. Each partition has one last boundary, so the choices cover all partitions without needing to enumerate every earlier boundary tuple again.

4. Base cases and computation order

   dp[0][0]=0; other zero-group prefixes are INF. Fill group layers g=1…K and prefix endpoints i=g…n. Every transition reads the previous completed layer. Store the minimizing j to reconstruct group endpoints backward from (K, n). Reverse those endpoints; they define all group ranges together with starting boundary zero.

5. Correctness and invariant

   Induction on g proves optimality:remove a partition’s last group to expose a valid smaller-layer state, or append that group to any candidate predecessor. No group is empty because j<i and j≥g−1. Unlike interval DP, this recurrence fixes a prefix and reads one previous-layer prefix state; it does not combine two arbitrary interval subproblems.

6. Work the example

   For [1,2,3,4] with K=2, the three possible cuts give costs 1²+9²=82,3²+7²=58, and 6²+4²=52. The optimum endpoints are 3 and 4. The table displays the group layers; INF means too few entries for the required number of nonempty groups.

   groups / prefix	0	1	2	3	4
   0	0	INF	INF	INF	INF
   1	INF	1	9	36	100
   2	INF	INF	5	18	52

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

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n,K;
    std::cin>>n>>K;
    std::vector<long long>prefix(n+1);
    for(int i=1;i<=n;++i){
        long long x;
        std::cin>>x;
        prefix[i]=prefix[i-1]+x;
    }
    const long long INF=4000000000000000000LL;
    std::vector<std::vector<long long>>dp(K+1,std::vector<long long>(n+1,INF));
    std::vector<std::vector<int>>split(K+1,std::vector<int>(n+1,-1));
    dp[0][0]=0;
    for(int g=1;g<=K;++g){
        for(int i=g;i<=n;++i){
            for(int j=g-1;j<i;++j){
                if(dp[g-1][j]!=INF){
                    long long sum=prefix[i]-prefix[j],candidate=dp[g-1][j]+sum*sum;
                    if(candidate<dp[g][i]){
                        dp[g][i]=candidate;
                        split[g][i]=j;
                    }
                } // Exactly g nonempty contiguous blocks.
            }
        }
    }
    std::vector<int>ends;
    for(int g=K,i=n;g>0;--g){
        ends.push_back(i);
        i=split[g][i];
    }
    std::reverse(ends.begin(),ends.end());
    std::cout<<dp[K][n]<<'\n';
    for(int i=0;i<K;++i){
        std::cout<<ends[i]<<(i+1==K?'\n':' ');
    }
}

Complexity analysis

O(Kn) states with O(n) split transitions each:O(Kn²) time, O(Kn) values/parents plus O(n) prefix sums. Value-only computation can roll group rows to O(n) memory. Every cost≤(sum a)²≤9·10^10 fits long long.

Example input and output

Read n K (1≤K≤n≤300), then n nonnegative integers≤1000. Print minimum sum of squared block sums and K 1-based inclusive group endpoints.

Input

4 2
1 2 3 4

Output

52
3 4

For [1,2,3,4] with K=2, the three possible cuts give costs 1²+9²=82,3²+7²=58, and 6²+4²=52. The optimum endpoints are 3 and 4. The table displays the group layers; INF means too few entries for the required number of nonempty groups.

Practical applications

Use for ordered grouping, segmentation and prefix-based costs. Compare interval DP’s two-child splitting and knapsack’s item/resource model. The later optimized lesson uses this same nonnegative squared-sum cost to prove a valid monotonicity property.

Check your understanding

Why does the last-boundary loop stop at i−1?

Put it into practice

Enumerate every K−1 cut combination for a short array.