2.最小路径和

• $dp[i][j]=grid[i][j]+min(dp[i−1][j], dp[i][j−1])$

• 2.19

  • 初始化dp【i，0】【j，0】

• 2.4

  • 也要初始化第一行第一列，只不过需要计入步数的逻辑

• ？？。？ 但是注意——这个公式 不能直接用于最上面那一行和最左边那一列，因为：

  • 最上面那一行的格子 没有上方格子；
  • 最左边那一列的格子 没有左边格子。

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n]; 
        dp[0][0] = grid[0][0];
        //初始化第一行和第一列(也是走的状态公式)(不初始化时会像第一题一样越界)
        for(int j=1;j<n;j++){
            dp[0][j] = grid[0][j]+dp[0][j-1];
        }
        for(int i=1;i<m;i++){
            dp[i][0] = grid[i][0]+dp[i-1][0];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] =grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
}