代码随想录算法训练营Day39 | 动态规划(2/17) LeetCode 62.不同路径 63. 不同路径 II

来到动态规划的第二天练习了！

第一题

62.?Unique Paths

There is a robot on an?m x n?grid. The robot is initially located at the?top-left corner?(i.e.,?grid[0][0]). The robot tries to move to the?bottom-right corner?(i.e.,?grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers?m?and?n, return?the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to?2 * 10^9.

想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。

可以用递归的办法，很简洁的写出代码，但是会超时。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

用动态规划写出的代码如下：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        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.?Unique Paths II

You are given an?m x n?integer array?grid. There is a robot initially located at the?top-left corner?(i.e.,?grid[0][0]). The robot tries to move to the?bottom-right corner?(i.e.,?grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as?1?or?0?respectively in?grid. A path that the robot takes cannot include?any?square that is an obstacle.

Return?the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to?2 * 10^9.

这道题和上一题不同的是，加了障碍，有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。

if obstacleGrid[i][j] == 0:
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

所以完整代码为：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
            return 0
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 0:  
                dp[i][0] = 1
            else:
                break
        for j in range(n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]