上海的做网站的公司,上海十佳装修公司排名,网站建设费用如何收取,企业网站建设需了解什么LeetCode 62.不同路径#xff1a;
文章链接 题目链接#xff1a;62.不同路径
思路#xff1a;
动态规划 使用二维数组保存递推结果 ① dp数组及下标含义 dp[i][j]#xff1a;表明从(0, 0)到下标为(i, j)的点有多少条不同的路径 ② 递推式#xff1a; 机器人只能向下或向…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] 02)第二种初始化。 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开始
