Title Description

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 .

Their thinking

•   State definition ：grid [ i ][ j ] Defined as a point ( i , j ) Minimum path at ;
• State transition equation ： At this time, it is generally discussed in four categories

  • When both the left and upper edges are matrix boundaries ： When i = 0, j = 0 when , In fact, that is The starting point , grid [ i ] [ j ] = grid [ i ] [ j ];

  • When neither the left nor the upper edge is a matrix boundary ： When   i and j Not for 0 , grid [ i ] [ j ] = min( grid [ i -1 ] [ j ] , grid [ i ] [ j - 1] ) +  grid [ i ] [ j ];

  • When only the left is the matrix boundary ： Only from above , When i = 0, j It's not equal to 0 when ,  grid [ i ] [ j ] =  grid [ i ] [ j - 1] + grid [ i ] [ j ];

  • When only the upper edge is the matrix boundary ： Only from the left , When i Not for 0 , j = 0 when , grid [ i ] [ j ] =  grid [ i - 1] [ j ] + grid [ i ] [ j ];

• The final return value returns to the state in the lower right corner of the matrix ：return grid[m-1][n-1];

I / O example

Code

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];
    }
}