Finding the Minimum Path Sum in a Grid with Dynamic Programming

The algorithm of the day is a bit trickier than yesterday's:

given an m x n grid filled with non-negative numbers, find a path from the top left to the bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point.

For example, if you were given the input
[
[1,3,1],
[1,5,1],
[4,2,1]
]
the output should be 7, because the path that would produce the minimum sum would go 1 > 3 > 1 > 1 > 1.

The two main ways to solve this problem are Depth First Search and Dynamic Programming. Today, I'll be solving it using dynamic programming. First, I'll give a brief overview of what dynamic programming is. Then, I'll go over the general approach to this problem, and using JavaScript, I will solve the algorithm. Finally, I'll use an example and go through the problem, explaining each step.

What is Dynamic Programming?

You've probably done dynamic programming in the past, even if you've never heard the term before. As defined by Geeks for Geeks:

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

One common example of dynamic programming is the Fibonacci Problem. While you could solve for the nth Fibonacci number using recursion, the time complexity on that approach would be O(n^2). With dynamic programming, the time complexity would be O(n)--far preferable.

The Problem: Approaching It and Coding The Solution

The first thing I'll do is initiate a few variables that represent the rows and columns of the inputted grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  //...
}

Now, I want to create a new array called pathChange. The purpose of pathChange is to store the minimum sum path at each point in the inputted grid. Rather than modify the input, I'll make a new empty array which is the same size as the inputted grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  //...
}

Right now, we have an inputted grid, and an empty array of size m x n. The next thing to do is to set the starting square. Because, as per the algorithm instructions, we're beginning in the top left corner ([0][0]), we can initiate that point in the pathChange array to equal the value in the input grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  //...
}

Now we'll want to build the edges of the pathChange array. Because we know that we can only ever move down or right, these initiations are going to be pretty straightforward: in the first row, we can only move right, and in the first column, we can only move down. So, we can build two for loops--one for the first column, and one for the first row.

For the first column, we'll go down each space in the pathChange array, and set it equal to the element just above it in the pathChange array, plus that element in the grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  //...
}

Now, for the first row, we'll do a very similar thing: we'll move from left to right, and set each element in the pathChange array equal to the one just to its left, plus the element in that location in the grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  for (let i = 1; i < n; i++) {
    pathChange[0][i] = pathChange[0][i - 1] + grid[0][i];
  }

  //...
}

At this point, we have the top and left edges of the pathChange filled out with numbers representing the sum up to that point. All that's left to do is fill out the remainder of the pathChange array.

In order to find the minimum sum path of the remaining elements, we have to compare the element in the pathChange array just above and just to the left, and see which one is smaller. The reason we only compare these two is because, in the instructions, we can only ever move down and to the right. So, using Math.min() and the same logic as before, we will add the smaller of the pathChange elements (either the one from above or from the left) to the value of that element in the grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  for (let i = 1; i < n; i++) {
    pathChange[0][i] = pathChange[0][i - 1] + grid[0][i];
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      pathChange[i][j] =
        Math.min(pathChange[i - 1][j], pathChange[i][j - 1]) + grid[i][j];
    }
  }

  //...
}

Now, pathChange is complete. Because our target square is the one in the bottom right corner, we can just return the value at that point in the pathChange array.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  for (let i = 1; i < n; i++) {
    pathChange[0][i] = pathChange[0][i - 1] + grid[0][i];
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      pathChange[i][j] =
        Math.min(pathChange[i - 1][j], pathChange[i][j - 1]) + grid[i][j];
    }
  }

  return pathChange[m - 1][n - 1];
}

Walking Through an Example

I like using examples and visuals in order to better explain and understand tricky algorithms like this one. I'll start an inputted grid:
[
[1,3,1],
[1,5,1],
[4,2,1]
].
The first few lines of the function establish m, n, and pathChange. Once pathChange is created in the size of the input array, we have a grid of size m x n, which is all filled out, as well as pathChange, which is the same size as the inputted grid, but is empty.

Now, we set pathChange[0][0] = grid[0][0].

Next, we go down the first column, and set each item equal to the last item in pathChange plus that location's value in the grid.

We'll do the same thing for the first row: set each item in pathChange equal to the last item in pathChange plus that location's value in the grid.

Now is time for the nested for loops. At the square [1][1] in pathChange, we will set it equal to the minimum of (2,4) plus 5, which means 2 + 5.

Now, at the square [1][2] in pathChange, we set it equal to the minimum of (5, 7) + 1.

At the square [2][1], we set it equal to the minimum of (6, 7) + 2.

Finally, at [2][2], we set it equal to the minimum of (6, 8) + 1.

And there's our expected output! Let me know in the comments if you have any questions or alternate approaches.

Comments

[Saloni Yadav]

I tried a similar logic without extra space:

var minPathSum = function(grid) {
    let m = grid.length; 
    let n = grid[0].length;
    for (let i=0; i<m; i++) {
        for (let j=0; j<n; j++) {
            if (i==0 && j==0)
                continue;

            if (i==0) {
                grid[i][j]+=grid[i][j-1];
            } else if(j==0) {
                grid[i][j]+=grid[i-1][j];
            } else {
                grid[i][j]+=Math.min(grid[i][j-1], grid[i-1][j]);
            }
        }
    }
    return grid[m-1][n-1];
};