题目
https://leetcode.cn/problems/unique-paths-ii/description/?envType=study-plan-v2&envId=dynamic-programming
题解
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
| class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m,n = len(obstacleGrid), len(obstacleGrid[0])
lst = [[0 for j in range(n)] for i in range(m)]
if obstacleGrid[m-1][n-1] == 1:
return 0
lst[m-1][n-1] = 1
for i in range(n-2,-1,-1):
if obstacleGrid[m-1][i] == 1:
lst[m-1][i] = 0
else:
lst[m-1][i] = lst[m-1][i+1]
for i in range(m-2,-1,-1):
if obstacleGrid[i][n-1] == 1:
lst[i][n-1] = 0
else:
lst[i][n-1] = lst[i+1][n-1]
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
if obstacleGrid[i][j] == 1:
lst[i][j] = 0
else:
if obstacleGrid[i+1][j] == 0:
lst[i][j] += lst[i+1][j]
if obstacleGrid[i][j+1] == 0:
lst[i][j] += lst[i][j+1]
return lst[0][0]
|
注意两个特殊测试用例
1、特殊情况[[0,0],[0,1]]
2、特殊情况[[1,0]]，返回的是[0][0]，而不是max