Project Euler Solution #81: Path sum: two ways

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

Solution

This is again a pretty good example of dynamic programming. Dynamic programming splits a huge problem into several small easily solvable sub-problems. If we knew the minimal paths from a certain cell when going down and going right, it would be easy on how to decide. So, if we start at the destination cell and looking left and up, we can add the destination cost to these two cells. Going left and up again simply adds the previous cells again.

More interesting is the case when we are diagonal to the goal. We now have two options, the right and down cases. Since we want to minimize the path cost, we add the minimum of these two neighbour cells to the regarded cell. 

Imagine, we have the provided data already loaded into an 80x80 array we can then work out the implementation like this:

function(M) {

  var n = M.length - 1;

  for (var i = n; i >= 0; i--) {

    for (var j = n; j >= 0; j--) {

      if (i < n && j < n) {
        M[i][j]+= Math.min(M[i + 1][j], M[i][j + 1])
      } else if (i < n) {
        M[i][j]+= M[i + 1][j];
      } else if (j < n) {
        M[i][j]+= M[i][j + 1];
      }
    }
  }
  return M[0][0];
}

We can loop separately through the corner cases of the verges, which makes the solution a bit more readable and saves some cycles:

function solution(M) {

  var n = M.length - 1;

  for (var i = n - 1; i >= 0; i--) {

    M[n][i]+= M[n][i + 1];
    M[i][n]+= M[i + 1][n];
  }

  for (var i = n - 1; i >= 0; i--) {

    for (var j = n - 1; j >= 0; j--) {
      M[i][j]+= Math.min(M[i + 1][j], M[i][j + 1])
    }
  }
  return M[0][0];
}