给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。
样例
注意
你在同一时间只能向下或者向右移动一步
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| 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];
}
}
|