LeetCode：63. 不同路径 II（python）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode：63. 不同路径 II（python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4747字，纯文字阅读大概需要7分钟。
内容图文
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
内容总结
以上是互联网集市为您收集整理的LeetCode：63. 不同路径 II（python）全部内容，希望文章能够帮你解决LeetCode：63. 不同路径 II（python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】