63. 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?
avatar
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
Note: m and n will be at most 100.
Example 1:
Input:
[
[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
First
dp[j]代表当前行为0,1,2,3...n时，到达第j列的所有可能走法。
这道题比上一道题 62. Unique Paths 多了一个障碍物的条件。当遇见障碍物时，
那么当前从起点到障碍物的可能走法为0。
比如当前obstacleGrid[3][4]为障碍物，
从这位置往下、往右都无法前进，那么：
- Sum(obstacleGrid[4][4]) 的所有可能走法只等于Sum(obstacleGrid[4][3])。
- Sum(obstacleGrid[3][5]) 的所有可能走法只等于Sum(obstacleGrid[2][5])。
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
r, c = len(obstacleGrid), len(obstacleGrid[0])
dp = []
flag = 1
for i in range(c):
if obstacleGrid[0][i]:
flag = 0
dp.append(flag)
for i in range(1, r):
dp[0] = int(not obstacleGrid[i][0] and dp[0])
for j in range(1, c):
if obstacleGrid[i][j]:
dp[j] = 0
else:
dp[j] = dp[j-1] + dp[j]
return dp[-1]
s = Solution()
print(s.uniquePathsWithObstacles(
[[0,1,0,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]))
