题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

解题思路

•  状态定义：grid [ i ][ j ] 被定义为点( i , j )处的最小路径；
• 状态转移方程：此时一般要分四类情况讨论

  • 当左边和上边都是矩阵边界时： 即当 i = 0, j = 0时，其实就是起点， grid [ i ] [ j ] = grid [ i ] [ j ]；

  • 当左边和上边都不是矩阵边界时： 即当  i 和 j 都不为 0 ， grid [ i ] [ j ] = min( grid [ i -1 ] [ j ] , grid [ i ] [ j - 1] ) +  grid [ i ] [ j ]；

  • 当只有左边是矩阵边界时： 只能从上面来，即当 i = 0, j 不等于 0 时，  grid [ i ] [ j ] =  grid [ i ] [ j - 1] + grid [ i ] [ j ]；

  • 当只有上边是矩阵边界时： 只能从左面来，即当 i 不为 0 , j = 0 时， grid [ i ] [ j ] =  grid [ i - 1] [ j ] + grid [ i ] [ j ]；

• 最终返回值返回矩阵右下角的状态即可：return grid[m-1][n-1];

输入输出示例

代码

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int 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];
                else if(i == 0){
                    grid[i][j] = grid[i][j-1] + grid[i][j];
                }else if(j == 0){
                    grid[i][j] = grid[i-1][j] + grid[i][j];
                }else {
                    grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
                }
            }
        }
        return grid[m-1][n-1];
    }
}