1. ＜ tag dynamic programming and path combination problem ＞ lt.62 Different paths + lt.63 Different paths II

lt.62. Different paths

[ Case needs ]

[ Train of thought analysis 1 , Abstract as a tree DFS]

[ Code implementation ]

[ Train of thought analysis II , Dynamic programming ]

• Robot from (0,0) Set out , arrive (m-1, n-1) Midpoint ;
• According to the five parts of dynamic rules :

1. determine dp The meaning of array and its subscript :

dp[i][j]: From (0, 0) set out , To (i,j) Yes dp[i][j] Different paths

2. Determine the recurrence formula

Want to ask for dp[i][j], It can only be derived from two directions ( Down and right ), namely dp[i - 1][j] and dp[i][j - 1];
Take a look back. dp[i - 1][j] What does it mean , It's from (0, 0) It's in (i - 1, j) There are several paths ,dp[i][j - 1] Empathy .

3. dp Initialization of an array

How to initialize , First dp[i][0] Some are 1, Because from (0, 0) It's in (i, 0) There's only one way to go , that dp[0][j] Also in the same way . Notice the path , Not the number of steps
So the initialization code is ：

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

4. Determine the traversal order

Here's a look at the recursive formula dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j] It's all derived from above and to the left , Then it's OK to traverse one layer from left to right .
So you can guarantee that the derivation dp[i][j] When ,dp[i - 1][j] and dp[i][j - 1] There must be a number .

5. Give an example to deduce dp Array
   

[ Code implementation ]

class Solution {
    
    public int uniquePaths(int m, int n) {
    
        //1. dp Array :  Go to the (i,j) How many steps are needed 
        int[][] dp = new int[m][n];
        //2.  The recursive formula 
        //dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //3. dp How to initialize an array 
        for(int i = 0; i < m; i++){
    dp[i][0] = 1;}
        for(int j = 0; j < n; j++){
    dp[0][j] = 1;}
        //4.  Determine the traversal order 
        // From left to right, one floor at a time ( From the top down ) Traverse 
        for(int i = 1; i < m; i++){
    
            for(int j = 1; j < n; j++){
    
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
        //5.  Give an example to deduce dp Array 
    }
}

• Complexity of time and space
  

lt.63. Different paths II

[ Case needs ]

[ Thought analysis ]

[ Code implementation ]

class Solution {
    
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
        //1.  determine dp Array and initialize 
        //dp[i][j] From [0][0]  To [i][j] How many paths are there 
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // An extra pruning operation 
        if(obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1)return 0;


        int[][] dp = new int[m][n];

        //2.  Deterministic recursion 
        // dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //3.  The initial value of the array . dp[0][j] = 1; dp[i][0] = 1;
        // namely  [0][0] Go to his row or column ,  The paths are all for 1
        // This question sets up obstacles ,  So add judgment ( Where there are no obstacles, there will be initial values )
        for(int i = 0; i < m; i++){
    
            if(obstacleGrid[i][0] == 1)break;
            dp[i][0] = 1;
        }

        for(int j = 0; j < n; j++){
    
            if(obstacleGrid[0][j] == 1)break;
            dp[0][j] = 1;
        }

        //4.  evaluation 
        for(int i = 1; i < m; i++){
    
            for(int j = 1; j < n; j++){
    
                if(obstacleGrid[i][j] != 1){
    
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}