Q63-不同路径II-中等-动态规划

63. 不同路径 II

Question

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

Example 1:

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右

Example 2:

输入：obstacleGrid = [[0,1],[0,0]] 输出：1

Note:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

Approach 1: 动态规划

这道题在Q62的基础上设置了障碍物，思路比较简单，只需在动态规划迭代之前先判断知否存在障碍物即可。本题目是典型的动态规划问题，因为我们计算到每个格子的路线数目可以通过，之前格子的可到达路线数目计算。具体计算迭代方式如下：

用dp[m][n]记录到达每个位置的路径数目（注意，agent只能右移或者下移）。 考虑边界条件，将dp[0][j]和dp[i][0]单独赋值为1。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid) -> int:

        m,n = len(obstacleGrid),len(obstacleGrid[0])
        if obstacleGrid[m-1][n-1] == 1 or obstacleGrid[0][0] == 1:
            return 0

        dp = [[0]*n for _ in range(m)]
        dp[0][0] = 1

        for i in range(m):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = 1
            else:
                break
        for j in range(n):
            if obstacleGrid[0][j] != 1:
                dp[0][j] = 1
            else:
                break

        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]


def main():
    mat = [[0,0,0],[0,1,0],[0,0,0]]
    solution=Solution().uniquePathsWithObstacles(mat)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

• 时间复杂度：。

• 空间复杂度：，即为存储所有状态需要的空间。注意到dp[i][j]仅与第i行和第i-1行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换m和n使得 m n，这样空间复杂度降低至 。