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

62.不同路径 - 🔗

讲解 - 🔗
💡动规五部曲：
1. 确定dp数组（dp table）以及下标的含义 - dp[i][j]表示走到第i行第j列有几条路径
2. 确定递推公式 - dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
3. dp数组如何初始化 - 第一行和第一列均为1
4. 确定遍历顺序 - i, j 都从小到大
5. 举例推导dp数组

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 确定dp数组（dp table）以及下标的含义 - dp[i][j]表示走到第i行第j列有几条路径
        # 确定递推公式 dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        # dp数组如何初始化 - dp[0][0] = 0, dp[0][1] = 1, dp[1][0] = 1
        # 确定遍历顺序 - i, j 都从小到大
        # 举例推导dp数组

        dp = [[0] * n for _ in range(m)] # 初始化一个 m*n 的二维数组
        
        for i in range(m):
            for j in range(n):
                if not i or not j:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        return dp[m - 1][n - 1]

63. 不同路径 II - 🔗

讲解 - 🔗
💡动规五部曲：
1. 确定dp数组（dp table）以及下标的含义 - dp[i][j]表示走到第i行第j列有几条路径
2. 确定递推公式 - 分四种情况：

• 当前位置有障碍（即obstacleGrid[i][j] == 1）： 说明这条路走不通，dp[i][j] = 0
• 当前位置没有障碍：
• • 当前位置为第一行第一列：默认dp[0][0] = 1
• • 当前位置处于第一行第一列，且前一个位置没有障碍物：默认dp[i][j] = 1。可以想象一下，假设当前位置是第一行第三列，但是第一行第二列有障碍物，那么就没有路径可以走到第一行第三列。
• • 其他情况：dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

3. dp数组如何初始化 - dp = [[0] * n for _ in range(m)]
4. 确定遍历顺序 - i, j 都从小到大
5. 举例推导dp数组

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        # 确定dp数组（dp table）以及下标的含义 - dp[i][j]表示走到第i行第j列有几条路径
        # 确定递推公式 dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        # dp数组如何初始化 - dp[0][0] = 0
        # 确定遍历顺序 - i, j 都从小到大
        # 举例推导dp数组
        dp = [[0] * len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]
        for i in range(len(obstacleGrid)):
            for j in range(len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 1: # 相当于此路不通, dp[i][j] 默认为0
                    continue 
                elif i == 0 and j == 0: # 初始化dp[0][0]
                    dp[i][j] = 1
                elif (i == 0 and dp[i][j - 1] != 0) or (j == 0 and dp[i - 1][j] != 0):
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        return dp[-1][-1]