Topic37——64. Minimum path sum

subject ： Given a... That contains a nonnegative integer m x n grid grid , Please find a path from the top left corner to the bottom right corner , Make the sum of the numbers on the path the smallest .
explain ： You can only move down or right one step at a time .

 Example  1：

 Input ：grid = [[1,3,1],[1,5,1],[4,2,1]]
 Output ：7
 explain ： Because the path  1→3→1→1→1  The sum of is the smallest .

 Example  2：
 Input ：grid = [[1,2,3],[4,5,6]]
 Output ：12

Tips ：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

Double cycle ：

class Solution {
    
    public int minPathSum(int[][] grid) {
    
        for(int i = 0; i < grid.length; i++) {
    
            for(int j = 0; j < grid[0].length; j++) {
    
                int temp = Integer.MAX_VALUE;
                if(j-1 >= 0)
                    temp = Math.min(temp, grid[i][j-1]);
                if(i-1 >= 0)
                    temp = Math.min(temp, grid[i-1][j]);
                if(i-1 < 0 && j-1 < 0)
                    temp = 0;
                grid[i][j] = grid[i][j] + temp;
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

Official solution （ Improvement of the above method ）：

class Solution {
    
    public int minPathSum(int[][] grid) {
    
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < grid.length; i++) {
    
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1; j < grid[0].length; j++) {
    
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i = 1; i < grid.length; i++) {
    
            for(int j = 1; j < grid[0].length; j++) {
    
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}