T64. Minimum Path Sum【Medium】
题目
给出一个 m × n 的栅格，里面填着非负的数字。找到从左上角到右下角的最短（经过格子的数字之和最短）路径。
注意： 只能往右或者往下走。
思路
这题的思路是一个个往下遍历，分为三种情况来求到达那个格子的最短距离：
① 到第一行的格子只有一条路，所以到达的值 = 到左边格子的值 + 本格子的数
② 到第一列的格子只有一条路，所以到达的值 = 到上边格子的值 + 本格子的数
③ 到其他格子的方式简化为 两种，从左边来 和 从上面来 ，所以达到的值 = min(到左边格子的值,到上边格子的值) + 本格子的数
到这里思路就完了，看代码就好了~
代码
代码取自 Top Solution，稍作注释
public int minPathSum(int[][] grid) {
//得到行列长度
int m = grid.length, n = grid[0].length;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
//求出第一行第一列栅格的最小值
if(i == 0 && j != 0) grid[i][j] += grid[i][j-1];
if(i != 0 && j == 0) grid[i][j] += grid[i-1][j];
//其他栅格的最小值
if (i != 0 && j != 0) grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
}
}
//返回终点的最小值
return grid[m-1][n-1];
}
