题目要求
1
2
3
| 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.
|
计算从左上角到右下角的最短路径长度。只能向下或者向右移动。
类似的题目请参考我的博客Unique Path I 和 Unique Path II
思路和代码
同样，最左侧和最上侧的节点都只有一条路径可以到达，所以它们的路径唯一。其它的节点则可以通过左侧或上侧的节点到达。只需要判断左或上哪条路径更短即可。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int minPathSum(int[][] grid) {
int row = grid.length;
if(row==0){
return 0;
}
int column = grid[0].length;
for(int i = 1 ; i<row ; i++){
grid[i][0] += grid[i-1][0];
}
for(int i = 1 ; i<column ; i++){
grid[0][i] += grid[0][i-1];
}
for(int i = 1 ; i<row ; i++){
for(int j = 1 ; j<column ; j++){
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[row-1][column-1];
}
|