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.