Q63 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?

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```
解题思路：

Python 实现：
```class Solution:
# DP
# Time: O(n^2)
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
row = len(obstacleGrid)
col = len(obstacleGrid[0])
if obstacleGrid[row-1][col-1] == 1:
return 0
dp = [[0 for _ in range(col)] for _ in range(row)]
for i in range(row):  # 初始化第一行，遇到阻碍后面都是0
if obstacleGrid[i][0] == 0:
dp[i][0] = 1
else:
break
for j in range(col):  # 初始化第一列，遇到阻碍后面都是0
if obstacleGrid[0][j] == 0:
dp[0][j] = 1
else:
break
for i in range(1, row):
for j in range(1, col):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[i][j]

obstacleGrid1 = [[0,1,0],[0,1,0],[0,0,0]]
obstacleGrid2 = [[0,0,0],[0,1,0],[0,0,0]]
print(Solution().uniquePathsWithObstacles(obstacleGrid1))  # 1
print(Solution().uniquePathsWithObstacles(obstacleGrid2))  # 2```

173 篇文章42 人订阅

0 条评论

相关文章

PHP数据结构（十） ——有向无环图与拓扑算法

PHP数据结构（十）——有向无环图与拓扑算法 （原创内容，转载请注明来源，谢谢） 一、有向无环图概念 有向无环图又称为DAG图。与其对应的还有有向树、有环图。...

612110

15930

35220

49220

17220

39460

12920

17410

35690