每天一题LeetCode【第47天】

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]; 
}