Sword finger offer II 098 Number of paths / Sword finger offer II 099 Sum of minimum paths

The finger of the sword Offer II 098. Number of paths 【 Medium question 】

Ideas ：【 Dynamic programming 】

Second order dp Array ：
dp[i][j] Indicates walking from the upper left corner to the subscript (i,j) The number of paths required for the location of .

The boundary conditions ：
dp[0][0]=1

i = 0 when :
The end point is at the upper boundary of the matrix ,dp[i][j] The value of depends only on the left point dp
namely dp[0][j] = dp[0][j-1]

j = 0 when :
The end point is at the left boundary of the matrix ,dp[i][j] The value of depends only on the upper side point dp
namely dp[i][0] = dp[i-1][0]

In fact, if the points of the left boundary and the upper boundary start from the upper left corner , There is only one way to get there ,
namely dp[0][j] = 1,dp[i][0] = 1.

Transfer equation ：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Code ：

class Solution {
    
    public int uniquePaths(int m, int n) {
    
        // Dynamic programming 
        // Definition dp Array , Said go (i,j) Number of paths available for location 
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (i > 0 && j > 0){
    
                    // Transfer equation 
                    // Go to the (i,j) The number of paths to a position is determined by the number of paths to its left and upper sides 
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }else {
    
                    // The boundary conditions 
// //1. Starting point of upper left corner 
// if (i == 0 && j == 0){
    
// dp[0][0] = 1;
// }else if (i == 0){//2. Upper boundary 
// dp[0][j] = dp[0][j-1];
// }else {//3. Left boundary 
// dp[i][0] = dp[i-1][0];
// }
                    dp[i][j] = 1;
                }
            }
        }
        //(m-1,n-1) The location is m×n The lower right corner of the grid ,dp The number of paths of the array is always calculated from the upper left corner , therefore dp[m-1][n-1] That is, the total number of paths required by the topic 
        return dp[m-1][n-1];
    }
}

---

The finger of the sword Offer II 099. Sum of minimum paths 【 Medium question 】

Ideas ：【 Dynamic programming 】

Refer to the above question for solving ideas , take dp[i][j] The value of is defined as going from the upper left corner of the matrix to (i,j) The minimum path sum of the position is .

Code ：

class Solution {
    
    public int minPathSum(int[][] grid) {
    
        // Dynamic programming 
        // Exclude special inputs 
        if (grid == null || grid.length == 0 || grid[0].length == 0){
    
            return 0;
        }
        int m = grid.length,n = grid[0].length;
        // Define an array dp dp[i][j] Represents walking from the upper left corner of the matrix to (i,j) The minimum path and 
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (i > 0 && j > 0){
    
                    // Transfer equation 
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
                }else {
    
                    // The boundary conditions 
                    if (i == 0 && j == 0){
    
                        dp[0][0] = grid[0][0];
                    }else if (i == 0){
    
                        dp[0][j] = dp[0][j-1] + grid[0][j];
                    }else {
    
                        dp[i][0] = dp[i-1][0] + grid[i][0];
                    }
                }
            }
        }
        //dp[m-1][n-1] That is, the sum of the minimum paths from the upper left corner to the lower right corner of the matrix 
        return dp[m-1][n-1];
    }
}