DailyChallenge

63. Different paths II

20200706

Difficulty: Medium

Topic describes

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

Now consider that there are obstacles in the grid. So how many different paths are there going to be from the top left to the bottom right?

Obstacles and empty positions in the grid are represented by 1 and 0 respectively.

Note: The values of m and n are less than 100.

The sample1:

Input:[
  [0.0.0]. [0.1.0]. [0.0.0] ] Output:2 Explanation:3Right in the middle of the X3 grid is an obstacle.It's going from the top left to the bottom right2Different paths:1.Right -> right -> down -> down2.Down -> down -> right -> rightCopy the code

Solution

I grew up watching the video of snow vegetables. July was the DP topic, so I saw the YAN DP analysis of Xuexuecai in B station, and I was able to deal with the topic effectively for the time being, but I didn’t have enough questions. Try to do it with YAN DP analysis every day to deepen my understanding.

Yan DP analysis process

  1. State saiddp[i][j]Represents the number of ways to go to row I and column J, starting from row 0 and column 0; The property value is count
  2. State calculation: start at row 1 column
    • ob[i][j] == 1Means there is an obstacle, direct orderdp[i][j] = 0;
    • ob[i][j] == 0Means there are no obstacles,dp[i][j] = dp[i - 1][j] + d[i][j - 1]
  3. Initialization:
    • Row 0 and column 0 are traversed separately, and the value is 1; If you hit an obstacle, it’s all zero from this point on, because if you hit an obstacle, you’re not reachable after that
class Solution {
    public int uniquePathsWithObstacles(int[][] ob) {
        int m = ob.length;
        int n = ob[0].length;
        if(m == 0 || n == 0) return 0;
 / / ` ob [I] [j] = = 1 ` said no obstacle, ` dp [I] [j] = dp [I - 1) [j] + [I] [1] ` d  int[][] dp = new int[m][n];  / / initialization  // Row 0 and column 0 are traversed separately, and the value is 1;  // If you hit an obstacle, everything from this point on is 0, because you can't reach anything after that.  for(int i = 0; i < m; i++) {  if(ob[i][0] = =1) break;  else dp[i][0] = 1;  }  for(int i = 0; i < n; i++) {  if(ob[0][i] == 1) break;  else dp[0][i] = 1;  }   for(int i = 1; i < m; i++){  for(int j = 1; j < n; j++){  // 'ob[I][j] == 1', 'dp[I][j] = 0';  if(ob[i][j] == 1) dp[i][j] = 0;  / / ` ob [I] [j] = = 0 ` said no obstacle, ` dp [I] [j] = dp [I - 1) [j] + [I] [1] ` d  else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  }  }  return dp[m - 1][n - 1];  } } Copy the code

❝

My official account is GitKid

Temporarily share LeetCode every day, I am in the process of continuous learning, the public account is also constantly enriched, welcome everyone to scan code attention.

TODO: Dynamic programming topics

Wechat official account

This article is formatted using MDNICE