卖萌的弱渣

I am stupid, I am hungry.

Unique Path II

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

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

Example

There is one obstacle in the middle of a 3x3 grid as illustrated below.

1
2
3
4
5

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Solution

  • DP
  • Be carefur the case, dp[1][1], dp[i][1],dp[1][j] and dp[i][j]
(Unique-Path2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution:
    """
    @param obstacleGrid: An list of lists of integers
    @return: An integer
    """
    def uniquePathsWithObstacles(self, obstacleGrid):
        # write your code here
        # dp[i][j]: # of path at <i,j>
        # dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + 1
        row = len(obstacleGrid)
        col = len(obstacleGrid[0])
        dp = [[1]*(col+1) for i in range(row+1)]

        for i in range(1,row+1):
            for j in range(1,col+1):
                #dp[0][0]
                if i==1 and j==1:
                    dp[i][j] = 1-obstacleGrid[i-1][j-1]
                #dp[1][j]
                elif i==1:
                    if obstacleGrid[i-1][j-1]==1:
                        dp[i][j] = 0
                    else:
                        dp[i][j] = dp[i][j-1]
                #dp[i][1]
                elif j==1:
                    if obstacleGrid[i-1][j-1]==1:
                        dp[i][j] = 0
                    else:
                        dp[i][j] = dp[i-1][j]
                #dp[i][j]
                else:
                    if obstacleGrid[i-1][j-1] == 1:
                        dp[i][j] = 0
                    else:
                        dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[i][j]