title: Choose one element from each row and column in matrix and the sum is minimized
body: <p>If you have a NxN matrix of positive integers, and you are asked to select exactly one element from each row and column, so that the sum of the selected elements is minimized, how can it be solved?</p>
  
  <p>I think it is about Dynamic Programming. I have tried to minimize the time <code>O(n!)</code> using memoization:</p>
  
  <pre><code>    Dictionary&lt;byte[,], int&gt;[] memo = new Dictionary&lt;byte[,], int&gt;[17];
  
      int rec(byte[,] arr)
      {
          if (arr.Length == 1) return arr[0, 0];
          int opt = find(arr);
          if (opt != -1) return opt;
          opt = 1 &lt;&lt; 25;
          for (int i = 0; i &lt; arr.GetLength(1); ++i)
              opt = Math.Min(opt, arr[0, i] + rec(divide(arr, i)));
          add(arr, opt);
          return opt;
      }
  </code></pre>
  
  <p>This chooses an element from row 0 of the current matrix and then divides the matrix and calls itself recursively to solve the submatrix. Function <code>divide</code> divides the current matrix according to the selected element. The sub-matrix size is then (N-1)x(N-1). Function <code>find</code> performs linear search in <code>memo[n]</code>, and <code>add</code> adds the solution to <code>memo[n]</code> But this is too slow as it will compare each matrix with other.</p>
  
  <p>Do you have some inhancements? Is there a faster DP algorithm? Any help is appreciated</p>
  
  <p><strong>EXAMPLE</strong></p>
  
  <pre><code>1     2     3    4
  
  8     7     6    5
  
  9     11    10   12
  
  13    14    16   15
  </code></pre>
  
  <p>The optimal solution: 1 + 5 + 10 + 14</p>
  
  <p>Steps:</p>
  
  <pre><code>7   6  5
  
  11 10 12
  
  14 16 15
  </code></pre>
  
  <hr>
  
  <pre><code>11 10
  
  14 16
  </code></pre>
  
  <hr>
  
  <pre><code>14
  </code></pre>