Dynamic Programming Exercise

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.