LeetCode：63. 不同路径 II（python）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
思路：
-
递归（超时），递归遍历图的轨迹：从当前坐标的向右走的情况 + 从当前坐标向下走的情况
- 若当前位置超出边界或遇到障碍，则该路径失效，返回 0；
- 若当前位置到达目的地，且目的地有效（不为 1），则返回 1。
-
记忆递归，添加记忆字典
{(坐标):当前坐标路径数}。 -
动态规划
-
状态：图中位置，即每一处坐标，
dp数组表示当前位置的路径数。 -
选择：
- 当前位置不为障碍物时，当前位置的路径数为其向左位置和向右位置的路径数之和；
- 当前位置为障碍物时，当前位置的路径数为 0（不通）。
-
初始化：
-
dp数组维度为m×n（图的维度），值为0，表示路径数初始为0。 - 从坐标
(0, 0)处位置一直向右走，若未遇到障碍物，则将dp值设为1，表示有一条路径可达当前位置；若遇到障碍物，则跳出，表示当前位置不可达，路径数为0，且其后的向右位置亦不可达。 - 从坐标
(0, 0)处位置一直向下走（同上），若未遇到障碍物，则将dp值设为1，表示有一条路径可达当前位置；若遇到障碍物，则跳出，表示当前位置不可达，路径数为0，且其后的向下位置亦不可达。
-
-
返回值：目的地的路径数
dp[m-1][n-1]。
-
状态：图中位置，即每一处坐标，
- 优化空间的动态规划，将图作为动态转移数组，节省空间。
附代码1（Python3）：递归（超时）
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
if not obstacleGrid:
return 0
return self.recurve(0, 0, obstacleGrid)
def recurve(self, x, y, obstacleGrid):
if x==len(obstacleGrid) or y==len(obstacleGrid[0]) or obstacleGrid[x][y]==1: # 坐标超边界，或遇障碍物
return 0
if x==len(obstacleGrid)-1 and y==len(obstacleGrid[0])-1 and obstacleGrid[x][y]!=1: # 到达目的地，且目的地可达
return 1
return self.recurve(x+1, y, obstacleGrid)+self.recurve(x, y+1, obstacleGrid) # 递归向右走和向下走的情况
test = Solution()
obstacleGrid_li = [[[0,0,0],
[0,1,0],
[0,0,0]],
[[0,0],
[1,1],
[0,0]]
]
for obstacleGrid in obstacleGrid_li:
print(test.uniquePathsWithObstacles(obstacleGrid))
2
0
附代码2（Python3）：记忆递归
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
if not obstacleGrid:
return 0
memo = {} # 记忆
return self.memo_recurve(0, 0, obstacleGrid, memo)
def memo_recurve(self, x, y, obstacleGrid, memo):
if (x,y) in memo:
return memo[(x,y)]
if x==len(obstacleGrid) or y==len(obstacleGrid[0]) or obstacleGrid[x][y]==1:
memo[(x,y)] = 0
return memo[(x,y)]
if x==len(obstacleGrid)-1 and y==len(obstacleGrid[0])-1 and obstacleGrid[x][y]!=1:
memo[(x,y)] = 1
return memo[(x,y)]
memo[(x,y)] = self.memo_recurve(x+1, y, obstacleGrid, memo)+self.memo_recurve(x, y+1, obstacleGrid, memo)
return memo[(x,y)]
test = Solution()
obstacleGrid_li = [[[0,0,0],
[0,1,0],
[0,0,0]],
[[0,0],
[1,1],
[0,0]]
]
for obstacleGrid in obstacleGrid_li:
print(test.uniquePathsWithObstacles(obstacleGrid))
2
0
附代码3（Python3）：动态规划
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
if not obstacleGrid:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# 初始化 dp 数组
dp = [[0]*(n) for _ in range(m)]
for i in range(m): # 初始化 dp 数组的第 0 列
if obstacleGrid[i][0]==0:
dp[i][0] = 1
else:
break
for j in range(n): # 初始化 dp 数组的第 0 行
if obstacleGrid[0][j]==0:
dp[0][j] = 1
else:
break
# 动态转移
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j]!=1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
else:
dp[i][j] = 0
return dp[m-1][n-1]
test = Solution()
obstacleGrid_li = [[[0,0,0],
[0,1,0],
[0,0,0]],
[[0,0],
[1,1],
[0,0]]
]
for obstacleGrid in obstacleGrid_li:
print(test.uniquePathsWithObstacles(obstacleGrid))
2
0
附代码4（Python3）：优化空间的动态规划
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
if not obstacleGrid or obstacleGrid[0][0]==1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# 初始化 obstacleGrid 为 动态转移数组
path_flag = True
for i in range(m): # 初始化 dp 数组的第 0 列
if path_flag and obstacleGrid[i][0]==0:
obstacleGrid[i][0] = 1
else:
path_flag = False
obstacleGrid[i][0] = 0
path_flag = True
for j in range(1, n): # 初始化 dp 数组的第 0 行
if path_flag and obstacleGrid[0][j]==0:
obstacleGrid[0][j] = 1
else:
path_flag = False
obstacleGrid[0][j] = 0
# 动态转移
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j]!=1:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
else:
obstacleGrid[i][j] = 0
return obstacleGrid[m-1][n-1]
test = Solution()
obstacleGrid_li = [[[0,0,0],
[0,1,0],
[0,0,0]],
[[0,0],
[1,1],
[0,0]]
]
for obstacleGrid in obstacleGrid_li:
print(test.uniquePathsWithObstacles(obstacleGrid))
2
0