Given a *m* x *n* grid filled with non-negative numbers, find a path from top left to bottom right which *minimizes *the sum of all numbers along its path.

**Note:** You can only move either down or right at any point in time.

1. Recursive Solution

public int minPathSum(int[][] grid) { if (grid.length == 0 || grid[0].length == 0) { return 0; } int[][] resultMap = new int[grid.length][grid[0].length]; return minPathSum(grid, resultMap, grid.length-1, grid[0].length-1); } public int minPathSum(int[][] grid, int[][] resultMap, int row, int col) { if (row < 0 || col < 0) { return Integer.MAX_VALUE; } if (row == 0 && col == 0) { return grid[0][0]; } if (resultMap[row][col] == 0) { resultMap[row][col] = grid[row][col] + Math.min(minPathSum(grid, resultMap, row - 1, col), minPathSum(grid, resultMap, row, col - 1)); } return resultMap[row][col]; }

Note:

This is a very typical dp problem. where dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] ); To prevent same cell being visited and calculated multiple times, we have a resultMap 2d array to store the result. We also need to check the edge carefully to ensure the index is not out of bounds of the given array.

2. Iterative Solution (O(m*n) space)

public class Solution { public int minPathSum(int[][] grid) { if(grid.length==0||grid[0].length==0){ return 0; } //2D map -- O(m*n) space int[][] resultMap = new int[grid.length][grid[0].length]; resultMap[0][0] = grid[0][0]; //Calculate the first row for(int i = 1;i<grid[0].length;i++){ resultMap[0][i] = grid[0][i] + resultMap[0][i-1]; } //Calculate the first col for(int i = 1;i<grid.length;i++){ resultMap[i][0] = grid[i][0] + resultMap[i-1][0]; } //Calculate the rest for(int i=1;i<grid.length;i++){ for(int j=1;j<grid[0].length;j++){ resultMap[i][j] = grid[i][j]+Math.min(resultMap[i-1][j],resultMap[i][j-1]); } } return resultMap[grid.length-1][grid[0].length-1]; } }

Note: First calculate first row and first col which is there own grid value, then calculate other cells based on it.

3. *Optimal* Iterative Solution (O(n) space)

public class Solution { public int minPathSum(int[][] grid) { if (grid.length == 0 || grid[0].length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; //1D map -- O(n) space, n is # of cols int[] resultMap = new int[cols]; resultMap[0] = grid[0][0]; //Calculate the first row for (int i = 1; i < grid[0].length; i++) { resultMap[i] = grid[0][i] + resultMap[i - 1]; } for (int i = 1; i < rows; i++) { resultMap[0] = resultMap[0] + grid[i][0]; for (int j = 1; j < cols; j++) { resultMap[j] = grid[i][j] + Math.min(resultMap[j], resultMap[j - 1]); } } return resultMap[cols - 1]; } }

Note: You don’t necessarily need a 2d map to store which cost O(n) space where n is the # of columns. You can just use one row to stored the result of previous row, and replace the value with the current row from left to right one by one. One thing worth mentioning is this code is more space efficient though, it has lower readability.

More information and further thoughts for minimum path sum questions can be found here.