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 .

Ideas

Use dynamic programming to solve ：

1. The direction of the path can only be down or right
2. First row of grid Each element of can only be moved to the right from the upper left corner to , The first column of the grid Each element of can only be moved down from the upper left corner to , At this time The path is unique , Therefore, the sum of the minimum path corresponding to each element is the sum of the numbers on the corresponding path
3. Elements that are not in the first row or column ： With Move down one step from the adjacent element above arrive , perhaps Move one step to the right from its left adjacent element arrive , The minimum path corresponding to the element and be equal to The minimum value in the sum of the minimum path corresponding to the upper adjacent element and its left adjacent element plus the value of the current element
4. legend ： This is the first row and the first column ; The original array corresponds to dp Array is the synthesis of numbers on the corresponding path
   
5. as follows , Not in the first row and column ; This corresponds to dp The elements of the array are The minimum value in the sum of the minimum path corresponding to the upper adjacent element and its left adjacent element plus the value of the current element
   
   6. It can be seen from the above analysis , The equation is as follows ：
   

Code

class Solution {
    
    public int minPathSum(int[][] grid) {
    
        // If grid Array is empty 
        if(grid == null || grid.length == 0 || grid[0].length == 0){
    
            return 0;
        }
        // Get row and column 
        int rows = grid.length,clumns = grid[0].length;
        // Create target array 
        int[][] dp = new int[rows][clumns];
        // Assign values to the first row and first column elements 
        dp[0][0] = grid[0][0];
        // On the first line 
        for(int i=1;i<rows;i++){
    
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        // In the first column 
        for(int j=1;j<clumns;j++){
    
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        // Not the first row and the first column 
        // Circular row 
        for(int i=1;i<rows;i++){
    
            // Circular column 
            for(int j=1;j<clumns;j++){
    
                // Get the smallest value of the current element of the target array 
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[rows-1][clumns-1];

    }
}