一级a做片免费网站,自己做网站下载怎么,泰安网站优化,网站小图标怎么制作62.不同路径
题目链接
讲解链接
动归五部曲#xff1a; 1.确定dp数组及其下标的含义#xff1a;dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数#xff1b;
2.确定递推公式#xff1a;因为只能往右或者往下#xff0c;所以dp[i][j] dp[i - 1][j] dp[i][j - 1]。
3.…62.不同路径
题目链接
讲解链接
动归五部曲 1.确定dp数组及其下标的含义dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数
2.确定递推公式因为只能往右或者往下所以dp[i][j] dp[i - 1][j] dp[i][j - 1]。
3.dp数组初始化初始化为m * n的全1数组。
4.确定遍历顺序因为递推公式为dp[i][j] dp[i - 1][j] dp[i][j - 1]dp[i][j]都是从其上方和左方推导而来那么从左到右一层一层遍历就可以了。
5.举例推导dp数组m 3n 7时dp [[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]]
class Solution:def uniquePaths(self, m: int, n: int) - int:dp [[1] * n for _ in range(m)] # 初始化为全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[-1][-1]
63.不同路径Ⅱ
题目链接
讲解链接
本题大体思路同上只需要对障碍物处额外处理一下。
在初始化时如果第一列或第一行有障碍物则将该位置的dp至设为0在后续遍历过程中若遇到障碍物则同样将该位置设为0之后按照与上一题同样的方法计算即可。
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int:i, j 0, 0m, n len(obstacleGrid), len(obstacleGrid[0])dp [[0] * n for _ in range(m)]while i m and obstacleGrid[i][0] 0: # 初始化列第一列除了障碍物处均为1dp[i][0] 1i 1while j n and obstacleGrid[0][j] 0: # 同上第一行除障碍均为1dp[0][j] 1j 1for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] 1: # 若遇到障碍处则将该位置的dp置为0dp[i][j] 0else:dp[i][j] dp[i - 1][j] dp[i][j - 1] # 递推公式return dp[-1][-1]
