This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money

describe

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Copy the code

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Copy the code

Note:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1.
Copy the code

parsing

You can only walk in two ways: right and down at the top left corner. Finally, when you reach the bottom right corner, you can’t move forward if you encounter obstacles.

Experienced students all know that this is usually solved by dynamic programming, but when m and n are small, we can also find possible paths by backtracking and write recursive functions to solve the problem. In this case, m and n are relatively large, and the running result is also timeout, but it does not prevent us from trying to disintegrate in this way.

answer

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        M = len(obstacleGrid)
        N = len(obstacleGrid[0])

        def dfs(x, y):
            if x >= M or y >= N or x < 0 or y < 0:
                return 0
            if obstacleGrid[x][y] == 1:
                return 0
            if x == M - 1 and y == N - 1:
                return 1
            count = dfs(x + 1, y) + dfs(x, y + 1)
            return count

        return dfs(0, 0)
        	      
		
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

To solve the problem directly with dynamic programming, initialize a mxn-sized two-dimensional list dp, where each element represents how many different paths there are from the starting position to the current position. The idea is simple:

  • Iterate through the obstacleGrid[0]. If the element of index I is 0, it indicates that the path is open, then dp[0][I] is set to 1, if the element is 1, it indicates that the path is blocked, and the path to the right of the path is blocked all the time
  • Iterate through the elements in the first column of the obstacleGrid. If the element with index J is 0, it indicates that the path is open. Then dp[j][0] is set to 1
  • Start to traverse the obstacleGrid from position [1,1]. If the current element is 0, it indicates that the path is available. Then all paths from the start to the current location are DP [I][J-1] + dp[i-1][j]. Continue to iterate over the next element
  • At the end of traversal, the obtained dp[-1][-1] is the number of all different paths from the start position to the last end position

answer

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        M = len(obstacleGrid)
        N = len(obstacleGrid[0])
        dp = [[0]*N for _ in range(M)]
        for i,x in enumerate(obstacleGrid[0]):
            if x==0:
                dp[0][i] = 1
            else:
                break
        for j in range(M):
            if obstacleGrid[j][0] == 0:
                dp[j][0] = 1
            else:
                break
        for i in range(1,M):
            for j in range(1,N):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[-1][-1]
Copy the code

The results

Given in Python online submissions for Unique Paths II. Memory Usage: Submissions in Python online submissions for Unique Paths II.Copy the code

Similar to the topic

  • 62. Unique Paths
  • 980. Unique Paths III

Original link: leetcode.com/problems/un…

Your support is my biggest motivation