代码随想录学习Day 34

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 = 3，n = 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]