63. 不同路径II

leetcode python 数组动态规划中等

LeetCode

发布日期: 2020-10-19

更新日期: 2020-10-20

文章字数: 770

阅读时长: 3 分

阅读次数:

一、题目

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

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

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

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

说明： m 和 n 的值均不超过 100。

示例1：

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

二、思路

1. 动态规划

这道题与62题解题思路一样。网格中，第一行、第一列所以网格路径数都为1；其余网格，到达此网格的路径数等于其左侧网格路径数与上方网格路径之和。

与62题不同的在此题中存在障碍问题。但是解决方式没变。我们可以在输入的原二维数组dp中进行操作，假设障碍所在位置为i行j列。我们在每个网格位置上填入到达该位置的路径数，如果该位置是障碍，则该位置的值为0。具体如下：

首行、首列：当障碍出现在第一行、第一列，那么障碍后边的网格的路径将不再是1，而是0（包括障碍所在位置）。但是障碍之前的位置的值依然是1。
非首行首列：该位置的值等于左侧网格的值与上方网格的值之和。

我们可以得到状态转移方程为：

首行、首列i == 0 or j == 0的情况：
- 当i == 0:
  - 下标小于j的位置，dp[i][j] = 1
  - 小标大于等于j的位置，dp[i][j] = 0
- 当j == 0:
  - 下标小于i的位置，dp[i][j] = 1
  - 下标大于等于i的位置，dp[i][j] = 0
其余位置，dp[i][j] = dp[i-1][j] + dp[i][j-1]

三、代码

1. 动态规划

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 行数
        m = len(obstacleGrid)
        # 列数
        n = len(obstacleGrid[0])

        for i in range(m):
            for j in range(n):
                # 首行、首列
                if i == 0 or j == 0:
                    # 将障碍位置值重置为0
                    if obstacleGrid[i][j] == 1:
                            obstacleGrid[i][j] = 0
                    # 首列
                    elif i != 0 and obstacleGrid[i-1][j] == 0:
                        obstacleGrid[i][j] == 0
                    # 首行
                    elif j != 0 and obstacleGrid[i][j-1] == 0:
                        obstacleGrid[i][j] = 0
                    else:
                        obstacleGrid[i][j] = 1
                else:
                    if obstacleGrid[i][j] == 1:
                        obstacleGrid[i][j] = 0
                    else:
                        obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
        return obstacleGrid[-1][-1]