原題
現(xiàn)在考慮網(wǎng)格中有障礙物，那樣將會(huì)有多少條不同的路徑？
網(wǎng)格中的障礙和空位置分別用1和0來(lái)表示。
如下所示在3x3的網(wǎng)格中有一個(gè)障礙物：
[
[0,0,0],
[0,1,0],
[0,0,0]
]
一共有2條不同的路徑從左上角到右下角。
解題思路
- 同樣是矩陣型動(dòng)態(tài)規(guī)劃 - Matrix DP
- 對(duì)于有障礙物的地圖來(lái)說(shuō)涨缚，只需要把障礙物的坐標(biāo)設(shè)為0即可
- 要注意對(duì)第一行和第一列的初始化，如果遇到障礙物第一行后面和第一列下面都是0
完整代碼
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if not obstacleGrid or not obstacleGrid[0]:
return 0
m = len(obstacleGrid)
n = len(obstacleGrid[0])
cache = [[0 for i in range(n)] for j in range(m)]
flag1 = flag2 = 1
for j in range(m):
if obstacleGrid[j][0] == 1:
flag1 = 0
cache[j][0] = flag1
for i in range(n):
if obstacleGrid[0][i] == 1:
flag2 = 0
cache[0][i] = flag2
for j in range(1, m):
for i in range(1, n):
cache[j][i] = (cache[j - 1][i] + cache[j][i - 1]) if obstacleGrid[j][i] == 0 else 0
return cache[m - 1][n - 1]
