LeetCode_ 63_ Different paths II

Topic link

• https://leetcode.cn/problems/unique-paths-ii/

Title Description

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish”）.

Now consider the obstacles in the grid . So how many different paths will there be from the top left corner to the bottom right corner ？

Obstacles and empty positions in the grid are used respectively 1 and 0 To express .

Example 1：

 Input ：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
 Output ：2
 explain ：3x3  There is an obstacle in the middle of the grid .
 From the top left corner to the bottom right corner, there are  2  Different paths ：

1.  towards the right  ->  towards the right  ->  Down  ->  Down 
2.  Down  ->  Down  ->  towards the right  ->  towards the right 

Example 2：

 Input ：obstacleGrid = [[0,1],[0,0]]
 Output ：1

Tips ：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] by 0 or 1

Their thinking

Dynamic programming

• determine dp The meaning of arrays and subscripts
  • dp[i][j]： From (0,0) set out , To (i,j) Yes dp[i][j] There are different paths
• Determine the recurrence formula
  • Because only from left to right and from top to bottom , therefore dp[i][j] = dp[i-1][j] + dp[i][j-1]
  • There are obstacles here
• dp Initialization of an array
  • The first row and the first column have only one way to walk without encountering obstacles , But after encountering obstacles 0 A way to go
• Determine the traversal order
  • Two dimensional array , From left to right , Traverse layer by layer from top to bottom

AC Code

class Solution {
    
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
    
            if (obstacleGrid[i][0] == 1) {
    
                break;
            }
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
    
            if (obstacleGrid[0][i] == 1) {
    
                break;
            }
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
    
            for (int j = 1; j < n; j++) {
    
                if (obstacleGrid[i][j] == 0) {
    
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else {
    
                    dp[i][j] = 0;
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}