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

62.不同路径

https://leetcode.com/problems/unique-paths/

思路：这是一个比较简单的二维dp 问题， 机器人走到 [i][j] 这个格子有两种走法， 一种是从 i-1, j 过来， 一种是从 i，j-1过来。 所以到 i，j 的走法就是 到两个前置格子走法的和 （递推关系）。 然后注意dp数组初始化的边界条件， 即到 i=0 或者 j=0 的所以格子都只有一种走法。

难点： 无

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for 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]

63. 不同路径 II

 https://leetcode.com/problems/unique-paths-ii/description/

思路：和上一题是差不多的， 不同点是遇到障碍的话不能通行， 也就是到障碍的走法是 0. 这时候初始化就和上一题不同了， 不是到所有 i=0或者 j=0 都只有一种走法， 也可能是0个， 因为碰到障碍了。  这时候 i=0， 和 j =0 可以和其他格子用类似的推到。 初始化dp 数组的时候多加一行一列， 所以元素为0， 只有 i=-1， j =0 的时候为1. 等于给机器人留个入口。 

难点： 初始化dp数组和之前不太一样了。 

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        dp = [[0 for _i in range(len(obstacleGrid[0])+1)] for _j in range(len(obstacleGrid)+1)]
        if obstacleGrid[0][0] == 1:
            return 0
        else:
            dp[1][0] = 1
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if obstacleGrid[i-1][j-1] == 1:
                    continue
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]