LeetCode 62.不同路径:
文章链接
题目链接:62.不同路径
思路:
- 动态规划
使用二维数组保存递推结果
① 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]
- 数论的方法
从(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.不同路径Ⅱ
思路:
- 使用二维数组保存递推的结果
① 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]
- 使用一维数组保存递推的结果
如果使用一维数组保存递推的结果,实际上一维数组保存的是原二维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开始