Dynamic planning - 63. Different paths II

1 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 .

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

2 Title Example

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

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

3 Topic tips

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

4 Ideas

This question is relative to 62. Different paths (opens new window) There are obstacles .

Students who are exposed to this topic for the first time may be a little confused , There's an obstacle , What should I do ？

62. Different paths (opens new window) In, we have analyzed the situation of no obstacles in detail , If there are obstacles , In fact, it is the corresponding mark dp table（dp Array ） Keep the initial value (0) That's all right. .
Five steps of dynamic planning ：

determine dp Array （dp table） And the meaning of subscripts
dp[i][j] ： From （0 ,0） set out , To (i, j) Yes dp[i][j] Different paths .

Determine the recurrence formula
Recurrence formula and 62. Different paths are the same ,dp[i][j] = dp[i - 1][j] + dp[i][j - 1].

But here's a point to note , Because there are obstacles ,(i, j) If it's an obstacle, you should keep the initial state （ The initial state is 0）.
So the code is ：

if (obstacleGrid[i][j] == 0) {
     //  When (i, j) When there are no obstacles , Re derivation dp[i][j]
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}

From recursive formula dp[i][j] = dp[i - 1][j] + dp[i][j - 1] It can be seen that , It must be traversing from left to right , This ensures that the derivation dp[i][j] When ,dp[i - 1][j] and dp[i][j - 1] There must be a value .

The subject is 62. Different paths (opens new window) Obstacle version of , The overall thinking is generally the same .

But even if I did 62. Different paths , When doing this problem, you will also feel that you have no way to start when you encounter obstacles .

In fact, just consider , Encounter obstacles dp[i][j] keep 0 That's all right. .

There are also some small details , for example ： Initialization part , It's easy to ignore the obstacles. They should all be 0 The situation of .

The idea of this topic is taken from the code Capriccio
link ：https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html#%E6%80%9D%E8%B7%AF

5 My answer

class Solution {
    
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
	
        for (int i = 0; i < m; i++) {
    
	    if (obstacleGrid[0][i] == 1) break; // Once you encounter obstacles , The follow-up will not arrive 
	    dp[0][i] = 1;
        }
        for (int i = 0; i < n; i++) {
    
	    if (obstacleGrid[i][0] == 1) break;  Once you encounter obstacles , The follow-up will not arrive 
	    dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
    
            for (int j = 1; j < m; j++) {
    
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n - 1][m - 1];
    }
}