64. 最小路径和

image.png

解题思路

思路：
从右下往左上找，用dp数组来保存右下元素到括号指定点的距离
遍历整个矩阵，分四种情况：
1：仅仅代表最后一个元素
2：最后一行，但不是最后一列,图中的2到4
3：最后一列，但不是最后一行，图第三行的1到第二行的1
4：不是边界，比如5到1

代码

class Solution {
    public int minPathSum(int[][] grid) {
    int  [][] dp=new int[grid.length][grid[0].length];//dp数组来保存右下元素到括号指定点的距离
    //在二维数组中，grid.length代表有多少行，指里边的中括号
    //grid[0].length指第一行的元素个数，那不就是几列吗
    for(int i=grid.length-1;i>=0;i--){//是从右下到左上，反方向
        for(int j=grid[0].length-1;j>=0;j--){
           if(i==grid.length-1&&j==grid[0].length-1)
                dp[i][j]=grid[i][j];//仅仅代表最后一个元素
           if(i==grid.length-1&&j!=grid[0].length-1) //最后一行，但不是最后一列,图中的2到4
                 dp[i][j]=dp[i][j+1]+grid[i][j];//只能向右走
           if(i!=grid.length-1&&j==grid[0].length-1)//最后一列，但不是最后一行，图第三行的1到第二行的1
                 dp[i][j]=dp[i+1][j]+grid[i][j];//只能向下走
            if(i!=grid.length-1&&j!=grid[0].length-1)//不是边界，比如5到1
                 dp[i][j]=Math.min(dp[i][j+1]+grid[i][j],dp[i+1][j]+grid[i][j]);//有两个方向，选一个最小的
                
        }
    }
       return dp[0][0];
     }
}