力扣刷题64.最小路径和

本题目属于动态规划问题 对于网格上的第一行元素，只能通过左上角元素向右移动到达，对于网格上的第一列元素，只能通过左上角元素向下移动到达。

对于不在第一行和第一列的元素，可以通过其上面元素向下移动，或者其左方元素向右移动。

每个元素对应的最小路径与其相邻元素对应的最小路径和有关，所以可以用动态规划求解。

class Solution {
          
   
    public int minPathSum(int[][] grid) {
          
   
       if(grid == null || grid.length == 0 || grid[0].length == 0){
          
   
           return 0;
       }
       int rows = grid.length;
       int columns = grid[0].length;
       int[][] dp = new int[rows][columns];
       dp[0][0] = grid[0][0];
       //对应第一行
       for(int i = 1; i<rows; i++){
          
   
           dp[i][0] = dp[i-1][0]+grid[i][0];
       }
       //对应第一列
       for(int i= 1; i<columns; i++){
          
   
           dp[0][i] = dp[0][i-1] + grid[0][i];
       }
       //对应于其他普通元素
       for(int i = 1; i<rows; i++){
          
   
           for(int j = 1; j<columns; j++){
          
   
               dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
           }
       }
       return dp[rows-1][columns-1];
    }
}