給定一個只含非負整數(shù)的m*n網(wǎng)格蜜氨，找到一條從左上角到右下角的可以使數(shù)字和最小的路徑草娜。
樣例
注意
你在同一時間只能向下或者向右移動一步
public class Solution {
/**
* @param grid: a list of lists of integers.
* @return: An integer, minimizes the sum of all numbers along its path
*/
public int minPathSum(int[][] grid) {
if(null == grid)
return 0;
int row = grid.length;
int col = grid[0].length;
if(row <= 0 || col <= 0)
return 0;
int[][] steps = new int[row][col];
steps[0][0] = grid[0][0];
for(int i = 1;i < row;i++)
{
steps[i][0] += steps[i - 1][0] + grid[i][0];
}
for(int i = 1;i < col;i++)
{
steps[0][i] += steps[0][i - 1] + grid[0][i];
}
for(int i = 1;i < row;i++)
{
for(int j = 1;j < col;j++)
{
steps[i][j] = Math.min(steps[i - 1][j], steps[i][j - 1]) + grid[i][j];
}
}
return steps[row - 1][col - 1];
}
}
