﻿ How to understand linear partitioning in dynamic programming

# How to understand linear partitioning in dynamic programming

a couple days ago I learned about linear partitioning problem, here is my code for it, is this code right and I don't understand the formula behind it, why is it like that, if you are able please explain me why the formula works.

``````for(int i=1;i<=n;i++) {
rsq[i]=rsq[i-1]+arr[i];
}

int dp[n+1][k+1];
for(int i=0;i<=n;i++) {
for(int j=0;j<=k;j++) {
dp[i][j]=987654321;
}
}
dp[0][0]=0;
for(int i=1;i<=n;i++) {
dp[i][1]=rsq[i];
}
for(int i=1;i<=k;i++) {
dp[1][i]=arr[1];
}

for(int i=2;i<=n;i++) {
for(int j=2;j<=k;j++) {
for(int x=1;x<i;x++) {
int s=max(dp[x][j-1], rsq[i]-rsq[x]);
if(dp[i][j]>s) dp[i][j]=s;
}
}
}
cout<<dp[n][k];
``````

Following this explanation, apparently the semantics of the state space `dp` as follows; apparently `arr` contains the sizes of the items to process and `rsq` contains the partial sums needed below to circumvent their recalculation.

``````dp[i][j] = minimum possible cost over all partitions of
arr[1],...arr[i] into j ranges
where i in {1,...,n} and j in {1,...k} or positive
infinity if such a partition does not exist
``````

Apparently in the implementation `987654321` is used to model the value of positive infinity. Note that in the explanation, the axes of the state space are exchanged compared to the implementation in the original question. Based on this definition, we obtain the following recurrence relation for the values of the states.

``````dp[i,j] = min{ max{ dp[i-1,j'], sum_{i'=j'+1}^{n} arr[i']} : j' in {1,...,j} }
``````

In the implementation, the sum above is precalculated in `rsq`. The recurrence relation can be interpreted as follows. Given all values of `dp[i-1][*]` for some specific value of `i` (which means that all cost values for items `1` up to `i-1` are known), all values `dp[i][*]` (for items `1` up to `i`) can be obtained by taking all items from `j'+1` to `n'` (`j'` ranges from `j` to `j`, all possibilies are considered) and summing up the remainig items (which then consitute a partition); for the optimal partition of the first items, the precalculated value is used. The maximum of these values is the cost of the choice.

Intuitively, this can be seen as partitioning the items `arr[1],...,arr[n]` at an arbitrary split point. The items to the right are considered as one partition (the cost of which is the sum of their members, as they are placed together into one partition), the items to the left are recursively partitioned optimally into one partition less. The dynamic programming algorithm (besides the precalculation of the partial sums) initializes some base cases which corrspond to placing every item in a single partition and organizes the order of evaluation of the states in such a way that all values needed for the next larger value `j` of the second axis are always calculated when needed.