LeetCode_Unique Paths II

Posted on | In | Views:

Unique Paths II

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?
（不同的路径II，只能向右或者向下移动在有路障的情况下从左上角移动到右下角的路径个数）

Example:



1. 动态规划

写出其动规表达式 dp[i][j] = dp[i-1][j] + dp[i][j-1]。但是需要另外考虑：

  1. 遇到路障时，dp[i][j] = 0，继续扫描。
  2. 由于从左上角开始扫描，在扫描第一行时：dp[i][j] = dp[i][j-1]。
  3. 在扫描第一列时：dp[i][j] = dp[i-1][j] 。

具体实现形式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m, n = len(obstacleGrid), len(obstacleGrid[0])

        dp = [[1]*n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                    continue
                if i == 0 and j > 0:
                    dp[i][j] = dp[i][j-1]
                elif j == 0 and i > 0:
       		        dp[i][j] = dp[i-1][j]
                elif i > 0 and j > 0:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j]
                    
        return dp[m-1][n-1]