Dynamic Programming Exercise

Question

I have been struggling through a dynamic programming exercise and I can't seem to get the hold of it. I'll write here the problem and also it's solution stating explicitly what I don't understand.

We are given 2 sequences u1,u2,...,un and d1,d2,...,dm and a matrix of dimensions n x m built of positive integers C=[cij]. A list of k pairs ((ui1, dj1),(ui2,dj2),...,(uik,djk)) is said to be non-intersecting if i1 < 12 <..< ik and j1 < j2 <...< jk. The "compatibility of a list" is said to be the compatibility of the sum of the pairs that it is made of, that is Ci1j1 + Ci2j2 + ... + Cikjk

Example : Consider the matrix C = [Cij], so Cij = squared(i + j). Let i be i = 1, 2, 3, j = 1, 2, 3, 4 and k = 2. Some lists of 2 non-intersecting pairs are these ((u1, d2),(u3, d3)) with a compatibility of 9 + 36 = 45, ((u2, d2),(u3, d4)), with compatibility 16 + 49 = 65, and ((u1, d1),(u2, d4)), with compatibility of 4 + 36 = 40. Some lists that are not non-intersecting are the following : ((u2, d2),(u3, d1)),((u1, d4),(u3, d3)),((u3, d2),(u2, d3))

Solution:

M(i, j, t) = maximum cost of t non-intersecting pairs taken from ui,...,un and dj,...dm

Recurrence equation :
M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).}

• M(i, j, 0) = 0
• M(i, j, t) = −∞, if t > min{n − i + 1, m − j + 1}
• M(i, j, t) = 0, if i > n or j > m

I don't under the reccurrence very well and why do we assign −∞ to M(i, j, t) when t > min{n − i + 1, m − j + 1} but 0 when i > n or j > m

The solution is M(1, 1, k).

Answer 1

M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).}
           = max
             {
                 M(i+1, j+1, t-1) + c(i, j), <- we know the maximum cost of t-1 
                                                non-intersecting pairs taken from
                                                i+1,...,n and j+1,...,m to which
                                                we prepend the pair (i, j).
                 M(i, j+1, t), <- keep it at t elements and don't prepend anything,
                                  and take the one containing elements from
                                  i,...,n and j+1,...,m
                 M(i+1, j, t) <- same, but take elements from i+1,...,n and j,...,m
             }

This covers all cases: either we prepend the current element and increase the length by 1 or we don't increase the length and take the maximum of the possibilities this (lack of) action entails. You might ask "but what about M(i+1,j+1,t)? that's also a valid possibility." It is, but it's covered by the two other cases: M(i+1,j,t) will check M(i+1,j+1,t) and return it if needed. You could add it yourself to the recurrence, it wouldn't be wrong, just redundant.

why do we assign −∞ to M(i, j, t) when t > min{n − i + 1, m − j + 1}

Because you cannot have a solution in that case. At step i, you can only pick n - i + 1 elements from the first sequence (because you already picked up to i). Same for j. If t > min{n - i + 1, m - j + 1}, then you will not be able to pick the needed number of elements from one of the lists, and you mark that with negative infinity.

but 0 when i > n or j > m

This is just to handle out of range errors. I'm not sure why they choose 0, I would choose negative infinity for this as well just for consistency, or just avoid it altogether by putting conditions in the implementation (if i + 1 >= n then ignore this branch, although you'll still need to return 0/-infinity if none of the branches are valid), but it doesn't really matter.

If you return 0 and the answer is negative, then you'll run into problems. Of course, for your problem, due to the way C is built, we cannot have a negative solution (because C contains squares of numbers, which are >= 0 always). So you could go with 0 instead of negative infinity in the first case as well.

Exercise: can you write a similar recurrence, but for which the solution is given by M(n, m, k)? Define it in words first, and then mathematically.