How to understand linear partitioning in dynamic programming

Question

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];

Thanks in advance.

I'm not familiar with the problem itself; do you mean this problem? Apparently this is the same as the scheduling problem to minimize the makespan on identical parallel machines where the number of machines is part of the input, denoted as P||Cmax in the so-called three-field-notation. — Codor

Codor Codor · Accepted Answer · 2017-03-30T07:31:38

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.

How to understand linear partitioning in dynamic programming

1 Answers