Leetcode shahutong series -- 63. Different paths II

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/unique-paths-ii
 

Ideas ：

 Define a two-dimensional array  dp[][] ,dp[i][j]  From top left to top left   grid  (i,j)  How many paths are there in the location 

1.  initialization 
  1.1) dp[0][0] = 1
  1.2) dp[0][j] j > 0 && j < n,
     if  grid[0][j] = 0 , be  dp[0][j] = 1,
     if  grid[0][j] = 1,dp[0][j] = 0, ..., dp[0][n-1] = 0
  1.3) dp[i][0], i > 0 && i < m
     if  grid[i][0] = 0 , be  dp[i][0] = 1,
     if  grid[i][0] = 1,dp[i][0] = 0, ..., dp[m-1][n0] = 0
2.  State shift 
     if  grid[i][j] == 1,  be  dp[i][j] = 0;  That the road is blocked 
     if  grid[i][j] == 0,  dp[i][j] = dp[i-1][j] + dp[i-1][j]
3.  Return results  dp[m-1][n-1]

java Code ：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

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

        // 1.  initialization 
        boolean flag1 = true;
        for (int i = 0; i < m; i++) {
            if (flag1 && obstacleGrid[i][0] == 0) {
                dp[i][0] = 1;
            } else {
                flag1 = false;
            }
        }

        boolean flag2 = true;
        for (int j = 0; j < n; j++) {
            if (flag2 && obstacleGrid[0][j] == 0) {
                dp[0][j] = 1;
            } else {
                flag2 = false;
            }
        }

        // 2.  State shift 
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0; //  That the road is blocked 
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }


        // 3.  Return results 
        
        return dp[m-1][n-1];
    }
}