The Algorithm Design Manual Second Edition

{s

1

, . . . , s

i

} as equally as possible. This is a smaller instance of the same

problem, and hence can be solved recursively!

Therefore, let us define M [n, k] to be the minimum possible cost over all par-

titionings of

{s

1

, . . . , s

n

} into k ranges, where the cost of a partition is the largest

sum of elements in one of its parts. Thus defined, this function can be evaluated:

M [n, k] =

n

min

i=1

max(M [i, k

− 1],

n



j=i+1

s

j

)

We must specify the boundary conditions of the recurrence relation. These

boundary conditions always settle the smallest possible values for each of the argu-

ments of the recurrence. For this problem, the smallest reasonable value of the first

argument is n = 1, meaning that the first partition consists of a single element.

We can’t create a first partition smaller than s

1

regardless of how many dividers

are used. The smallest reasonable value of the second argument is k = 1, implying

that we do not partition S at all. In summary:

M [1, k] = s

1

, for all k > 0 and,

M [n, 1] =

n



i=1

s

i

By definition, this recurrence must return the size of the optimal partition.

How long does it take to compute this when we store the partial results? A total

of k

· n cells exist in the table. How much time does it take to compute the result

---

296

8 .

D Y N A M I C P R O G R A M M I N G

M [n



, k



]? Calculating this quantity involves finding the minimum of n



quantities,

each of which is the maximum of the table lookup and a sum of at most n



elements.

If filling each of kn boxes takes at most n

2

time per box, the total recurrence can

be computed in O(kn

3

) time.

The evaluation order computes the smaller values before the bigger values, so

that each evaluation has what it needs waiting for it. Full details are provided in

the code below:

partition(int s[], int n, int k)

{

int m[MAXN+1][MAXK+1];

/* DP table for values */

int d[MAXN+1][MAXK+1];

/* DP table for dividers */

int p[MAXN+1];

/* prefix sums array */

int cost;

/* test split cost */

int i,j,x;

/* counters */

p[0] = 0;

/* construct prefix sums */

for (i=1; i<=n; i++) p[i]=p[i-1]+s[i];

for (i=1; i<=n; i++) m[i][1] = p[i];

/* initialize boundaries */

for (j=1; j<=k; j++) m[1][j] = s[1];

for (i=2; i<=n; i++)

/* evaluate main recurrence */

for (j=2; j<=k; j++) {

m[i][j] = MAXINT;

for (x=1; x<=(i-1); x++) {

cost = max(m[x][j-1], p[i]-p[x]);

if (m[i][j] > cost) {

m[i][j] = cost;

d[i][j] = x;

}

}

}

reconstruct_partition(s,d,n,k);

/* print book partition */

}

This implementation above, in fact, runs faster than advertised. Our original

analysis assumed that it took O(n

2

) time to update each cell of the matrix. This

is because we selected the best of up to n possible points to place the divider, each

of which requires the sum of up to n possible terms. In fact, it is easy to avoid the

need to compute these sums by storing the set of n prefix sums p[i] =