代码随想录算法训练营第三十三天 | 62.不同路径 63.不同路径

LeetCode 62.不同路径：

文章链接
题目链接：62.不同路径

思路：

1. 动态规划
   使用二维数组保存递推结果
   ① dp数组及下标含义
   dp[i][j]：表明从(0, 0)到下标为(i, j)的点有多少条不同的路径
   ② 递推式：
   机器人只能向下或向右移动，因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
   ③ 初始化：
   应当初始化第一行和第一列均为1

for i in range(m)	dp[i][0] = 0	# 第一列
for i in range(n) dp[0][i] = 0	# 第一列

④ 遍历方式：
从左到右，从上往下遍历
⑤ 举例推导

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 and n == 1:return 1dp = [[1] * n for _ in range(m)]    # 第一行和第一列路径数都为1dp[0][0] = 1    # 出发点路径数为1for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]

dp数组可以简单为一维数组
按照从左到右，从上到下的遍历顺序
原dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
因此可以简化为一维数组。其中新dp[j]保存的是原dp[i - 1][j]
相当于dp[j]保存的是上一行的数据，从而dp[j] = dp[j] + dp[j - 1]

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 and n == 1:return 1dp = [1] * nfor i in range(1, m):for j in range(1, n):dp[j] += dp[j - 1]return dp[n - 1]

2. 数论的方法
   从(0, 0)到(m - 1, n - 1)一共 m + n - 2步，其中m - 1步为向下的。因此只要在m + n - 2中选择 m - 1步向下即可，即求组合C_{m + n - 2} ^ {m - 1}
   不能直接分别计算分子、分母后进行除法运算，会溢出，因此需要一边求分子一边对分子进行除法运算

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 and n == 1:return 1numerator = 1   # 分子denominator = m - 1     # 分母t = m + n - 2count = m - 1while count:numerator *= twhile denominator != 0 and numerator % denominator == 0:numerator = numerator // denominatordenominator -= 1t -= 1count -= 1return numerator

感悟：

简化dp数组以及使用数论的方法求

---

LeetCode 63.不同路径Ⅱ：

文章链接
题目链接：63.不同路径Ⅱ

思路：

1. 使用二维数组保存递推的结果
   ① dp数组及下标的含义：
   dp[i][j]：表示从(0, 0)到(i, j)的移动路径中没有障碍的路径数
   ② 递推式：
   机器人还是只能向下或向右移动，因此
   dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
   但是要求路径中不能有障碍，因此上式只能在(i, j)不为障碍时成立
   ③ 初始化：
   还是初始化横向和纵向的，但是遇到障碍后，后面的dp应当都为0
   
   1）第一种初始化
   dp[i][0] = dp[i - 1]0

dp[0][0] = 1
# 初始化第1列，行同理
for i in range(1, m):if obstacleGrid[i][0] == 0:dp[i][0] = dp[i - 1][0]else:dp[i][0] = 0

2)第二种初始化。
dp最开始时初始化为全0，遍历第1列时，遇到非障碍赋值为1，遇到障碍直接退出

dp = [[0] * n for _ in range(m)]
dp[0][0]
for i in range(1, m):if obstacleGrid[i][0] == 0:dp[i][0] = 1else:break 

④ 遍历方式：
从左到右，从上到下
⑤ 举例：

需要注意的是，初始化遍历时，第一种遍历方式dp[0][0] = 1，但是出发点是会有障碍的，因此需要先判断出发点是否有障碍再下一步初始化

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:if obstacleGrid[0][0] == 1: # 初始位置就有障碍return 0m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0] * n for _ in range(m)]    # 初始化为0dp[0][0] = 1# 初始化，遇到有障碍物之后的路径数均为0for i in range(1, m):  # 第0列if obstacleGrid[i][0] == 0:dp[i][0] = dp[i - 1][0]for j in range(1, n):  # 第0行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] == 0:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]

2. 使用一维数组保存递推的结果
   如果使用一维数组保存递推的结果，实际上一维数组保存的是原二维dp数组中上一行的结果，即一维数组的遍历是按行来的。
   初始化：和二维数组初始化方式相同，但是只初始化第1行
   递推：按行递推遍历时，j从0开始，因为一维数组保存的是原二维数组上一行的结果，因此dp[j] = dp[j] + dp[j - 1]仅在j != 0时成立， j = 0时，dp[j]直接继承上一行的结果不变

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:if obstacleGrid[0][0] == 1:return 0m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [0] * ndp[0] = 1for j in range(1, n):if obstacleGrid[0][j] == 0:dp[j] = 1else:breakfor i in range(1, m):for j in range(n):if obstacleGrid[i][j] == 1:dp[j] = 0elif j != 0:dp[j] += dp[j - 1]return dp[n - 1] 

感悟：

将二维dp数组降为一维dp数组

---

学习收获：

有障碍时对应的dp数组如何初始化，以及递推式如何变化。
以及将原本的二维dp数组降为一维dp数组时，遍历的话 j 从0开始