title: Find minimum sum of elements in a matrix
body: <p>Given a matrix, find the <strong>minimum sum</strong> of elements such that element is chosen from each row, and the adjacent element should not come from the same column. Assume the matrix only has 3 columns. </p>
  
  <pre><code>example 1:
  [[1, 2, 3], 
  
   [1, 2, 3], 
  
   [3, 3, 1]]
  
  minimum sum = 1 + 2 + 1 = 4  // matrix[0][0] + matrix[1][1] + matrix[2][2] or matrix[0][1] + matrix[1][0] + matrix[2][2]
  
  example 2:
  [[1, 100, 1], 
  
   [2, 99, 30],
  
   [100, 12, 13]]
  
  minimum sum = 1 + 2 + 12 = 15 // matrix[0][2] + matrix[1][0] + matrix[2][1]
  
  example 3:
  [[1, 2, 3], 
  
   [2, 5, 4],
  
   [2, 3, 1],
  
   [1, 6, 3]]
  
  minimum sum = 2 + 2 + 1 + 1 = 6 // matrix[0][1] + matrix[1][0] + matrix[2][2] + matrix[3][0]
  
  </code></pre>
  
  <p>Here's my code:</p>
  
  <pre><code>    public static int minCost(List&lt;List&lt;Integer&gt;&gt; matrix) {
          // Write your code here
          int rows = matrix.size();
  
          int[] cost = findMin(matrix.get(0), -1);
          int total = cost[0];
  
          for (int i = 1; i &lt; rows; i++){
              List&lt;Integer&gt; row = matrix.get(i);
              cost = findMin(row, cost[1]);
              total += cost[0];
          }
          return total;
      }
  
      private static int[] findMin(List&lt;Integer&gt; row, int col){
          int[] ans = new int[2];
          int min = Integer.MAX_VALUE;
          for (int i = 0; i &lt; row.size(); i++) {
              if (i == col){
                  continue;
              }
              if (row.get(i) &lt; min) {
                  min = row.get(i);
                  ans[0] = min;
                  ans[1] = i;
              }
          }
          return ans;
      }
  </code></pre>
  
  <p>I initially approached this question with Greedy, which is to find the minimum element in a row and the column of the element is different from that of the previous element. </p>
  
  <p>This method does not satisfy examples 2 and 3. I think dynamic programming would be the way to approach this problem but I am not sure how to construct the mem part. How to actually solve this problem with dynamic programming? Thanks in advance!</p>