本文主要是介绍代码随想录｜Day39｜动态规划 part02｜● 62.不同路径 ● 63. 不同路径 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
62.不同路径
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)] #如何构建一个矩阵
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
return dp[m - 1][n - 1]
【思考】 学习如何构建一个m行n列的表，注意dp[i][j - 1] + dp[i - 1][j] not dp[i][j - 1] + dp[j][i - 1] ！！！ 这道题我构建了初始化为全1的矩阵，对比下一题。
63. 不同路径 II
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
return 0
for i in range(m):
if obstacleGrid[i][0] == 0:
dp[i][0] = 1
else:
break #如果遇到障碍，这个点及后面的都是0
for i in range(n):
if obstacleGrid[0][i] == 0:
dp[0][i] = 1
else:
break
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
【思考】1. 第0行和第0列都是遍历不到的，需要初始化一下 ，和上一题不同，初始化矩阵为0比较方便，因为当遇到障碍物时，当前点及后面都要为0，而没有障碍物时，只需要当前点为1，后面还是0。初始化第0行和第0列很重要。
2. 遇到障碍物即可看作，当前点为0 就行。
这篇关于代码随想录｜Day39｜动态规划 part02｜● 62.不同路径 ● 63. 不同路径 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
