title: Dynamic Programming Exercise
body: <p>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.</p>
  
  <p>We are given 2 sequences <code>u1,u2,...,un</code> and <code>d1,d2,...,dm</code> and a matrix of dimensions <code>n x m</code> built of positive integers <code>C=[cij]</code>. A list of k pairs
   <code>((ui1, dj1),(ui2,dj2),...,(uik,djk))</code> is said to be non-intersecting if 
  <code>i1 &lt; 12 &lt;..&lt; ik</code> and <code>j1 &lt; j2 &lt;...&lt; jk</code>.
  The "compatibility of a list" is said to be the compatibility of the sum of the pairs that it is made of, that is <code>Ci1j1 + Ci2j2 + ... + Cikjk</code></p>
  
  <p>Example :
  Consider the matrix <code>C = [Cij]</code>, so <code>Cij = squared(i + j)</code>. Let i be
  <code>i = 1, 2, 3,  j = 1, 2, 3, 4</code> and <code>k = 2</code>. Some lists of 2 non-intersecting pairs are these <code>((u1, d2),(u3, d3))</code> with a compatibility of  <code>9 + 36 = 45</code>,
  <code>((u2, d2),(u3, d4))</code>, with compatibility <code>16 + 49 = 65,</code> and <code>((u1, d1),(u2, d4)),</code> with compatibility of <code>4 + 36 = 40</code>. Some lists that are not non-intersecting are the following : <code>((u2, d2),(u3, d1)),((u1, d4),(u3, d3)),((u3, d2),(u2, d3))</code></p>
  
  <p>Solution:</p>
  
  <p>M(i, j, t) = maximum cost of t non-intersecting pairs taken from ui,...,un and dj,...dm</p>
  
  <p>Recurrence equation :<br>
  <code>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).}</code></p>
  
  <ul>
  <li><code>M(i, j, 0) = 0</code></li>
  <li><code>M(i, j, t) = −∞, if t &gt; min{n − i + 1, m − j + 1}</code></li>
  <li><code>M(i, j, t) = 0, if i &gt; n or j &gt; m</code></li>
  </ul>
  
  <p>I don't under the reccurrence very well and why do we assign <code>−∞</code> to <code>M(i, j, t)</code> when  <code>t &gt; min{n − i + 1, m − j + 1}</code> but 0 when <code>i &gt; n</code> or <code>j &gt; m</code></p>
  
  <p>The solution is M(1, 1, k).</p>