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.
Solution:
public class Solution {
public int minPathSum(int[][] grid) {
if(grid.length == 0 || grid[0].length==0)
return 0;
for(int row = 0; row<grid.length; row++)
{
for(int col=0; col<grid[0].length; col++)
{
if (col>0 && row>0)
grid[row][col] += Math.min(grid[row][col-1], grid[row-1][col]);
else if (col>0)
grid[row][col] += grid[row][col-1];
else if (row>0)
grid[row][col] += grid[row-1][col];
}
}
return grid[grid.length-1][grid[0].length-1];
}
}
No comments :
Post a Comment