62. 不同路径 - 力扣（LeetCode）
①确定dp数组以及下标的含义：
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
②确定递推公式：
像要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]；此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
③dp数组如何初始化；
首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理
④确定遍历顺序；
递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
⑤举例推导dp数组；
from typing import List
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)]
# 设置第一列
for i in range(m):
dp[i][0] = 1
# 设置第一行
for i in range(n):
dp[0][i] = 1
# 计算每一个单元格的路径数量
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 索引在位置[m-1][n-1]
return dp[m-1][n-1]
if __name__ == '__main__':
m = 3
n = 7
res = Solution().uniquePaths(m, n)
print(res)63. 不同路径 II - 力扣（LeetCode）
本题与上题LC62相比，就是多了一个障碍，但是没有障碍的我们上题已经分析过，对于有障碍的位置，就是对该位置进行标记，保持初始值（0）就可以了。
①确定dp数组以及下标的含义：
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
②确定递推公式：
递推公式和62.不同路径一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
但是由于存在障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）
③dp数组如何初始化；
从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。
④确定遍历顺序；
从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出，一定是从左到右一层一层遍历，这样保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。
⑤举例推导dp数组；
from typing import List
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# 网格的行数
m = len(obstacleGrid)
# 网格的列数
n = len(obstacleGrid[0])
# 如果起点或者终点有障碍物，直接返回0
if obstacleGrid[m-1][n-1] == 1 or obstacleGrid[0][0] == 1:
return 0
# 创建一个二维列表用于存数路径数
dp = [[0]*n for _ in range(m)]
# 设置起点的路径数为1
dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
# 计算第一列的路径
for i in range(1, m):
if obstacleGrid[i][0] == 0:
dp[i][0] = dp[i-1][0]
# 计算第一行的路径
for j in range(1, n):
if obstacleGrid[0][j] == 0:
dp[0][j] = dp[0][j-1]
# 计算其他位置的路径数
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 终点返回路径数
return dp[m-1][n-1]
if __name__ == '__main__':
obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
res = Solution().uniquePathsWithObstacles(obstacleGrid)
print(res)