Recurrence Relation for Dynamic Programming Exercise

Question

I received a dynamic programming assignment and I need help figuring out the recurrence relation. The problem is similar to the weighted interval problem, but it has a few additional restrictions:

• You are given a series of N time slots, each of the same duration.
• Each time slot k, 0 <= k < N, is given a positive weight W[k].
• For any time interval [i, j] with i < j, the weight W[i,j] of that interval is:
  W[i,j] = W[i+1] + W[i+2] + ... + W[j]
  Notice that the weight W[i] of the first time slot is not counted, hence any interval of length 1 has a weight of 0.

You are given a value T < N and asked to select exactly T time slots such that the sum of the selected time intervals is maximized.

Example: For N = 5, T = 4 and the weights W = (3, 9, 1, 1, 7), selecting W[0, 1] = 9 and W[3, 4] = 7 will give a maximum weight of 16.

Answer 1

This is a nice little problem... Define S(i, t) to be the max weight possible if the last slot (end of last range) selected was i and among the slots 0..i there are exactly t slots selected.

The DP decision is that we either add w[i] into S(i, t), or we do not because either slot i-1 was selected, or it was not. So we have:

S(i, t) = max ( S(i-1, t-1) + w[i], S(j, t-1) for j = t-2..i-2 )

Cases where t-1>i are meaningless. So the base case is S(i, 1) = 0 for 0 <= i < N, and successive columns (t = 2,...,T) of the DP table are each one shorter than the last. The desired answer is max ( S(j, T) for j = T-1..N-1 )

Happily you can arrange the computation so that the maxima are computed incrementally, run time is O(NT), and space is O(N)

Working out your example, the DP table looks like this:

               t = 
         1    2    3    4
       ------------------
i = 0 |  0
    1 |  0    9   
    2 |  0    1   10
    3 |  0    1    9   11
    4 |  0    7    9   16

The answer is max(11, 16) = 16