63. Unique Paths II 不同路径 II

Title

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

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

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

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

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

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2

解释:

3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

向右 -> 向右 -> 向下 -> 向下

向下 -> 向下 -> 向右 -> 向右

动态规划

如果我们熟悉这类问题，可以一眼看出这是一个动态规划问题。当我们不熟悉的时候，怎么想到用动态规划来解决这个问题呢？我们需要从问题本身出发，寻找一些有用的信息，例如本题中：

• (i,j) 位置只能从 (i - 1, j) 和 (i, j - 1) 走到，这样的条件就是在告诉我们这里转移是 「无后效性」 的，f(i, j) 和任何的 f(i’, j’)(i’ > i, j’ > j) 无关。
• 动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。

通常如果我们察觉到了这两点要素，这个问题八成可以用动态规划来解决。

Solve

我们用 f(i, j) 来表示从坐标 (0, 0) 到坐标 (i, j) 的路径总数，u(i, j) 表示坐标 (i, j) 是否可行，如果坐标 (i, j) 有障碍物，u(i, j) = 0，否则 u(i, j) = 1。

因为「机器人每次只能向下或者向右移动一步」，所以从坐标 (0, 0) 到坐标 (i, j) 的路径总数的值只取决于从坐标 (0, 0) 到坐标 (i - 1, j) 的路径总数和从坐标 (0, 0) 到坐标 (i, j - 1) 的路径总数，即 f(i, j) 只能通过 f(i - 1, j) 和 f(i, j - 1) 转移得到。

当坐标 (i, j) 本身有障碍的时候，任何路径都到到不了 f(i, j)，此时 f(i, j) = 0；下面我们来讨论坐标 (i, j) 没有障碍的情况：如果坐标 (i - 1, j) 没有障碍，那么就意味着从坐标 (i - 1, j) 可以走到 (i, j)，即 (i - 1, j) 位置对 f(i, j) 的贡献为 f(i - 1, j)，同理，当坐标 (i, j - 1) 没有障碍的时候，(i, j - 1) 位置对 f(i, j) 的贡献为 f(i, j - 1)。

综上所述，我们可以得到这样的动态规划转移方程：

$$dp[i][j]=\{\begin{array}{ll}0,& u(i,j)=0\\ f(i-1,j)+f(i,j-1),& u(i,j)!=0\end{array}$$

很显然我们可以给出一个时间复杂度 O(nm) 并且空间复杂度也是 O(nm) 的实现，由于这里 f(i, j) 只与 f(i - 1, j) 和 f(i, j - 1) 相关，我们可以运用「滚动数组思想」把空间复杂度优化称 O(m)。

Code

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:rows, cols = len(obstacleGrid), len(obstacleGrid[0])dp = [1] + [0] * colsfor i in range(0, rows):for j in range(0, cols):dp[j] = 0 if obstacleGrid[i][j] else dp[j] + dp[j - 1]return dp[-2]

复杂度分析

时间复杂度：O(nm)，其中 n 为网格的行数，m 为网格的列数。我们只需要遍历所有网格一次即可。
空间复杂度：O(m)。利用滚动数组优化，我们可以只用 O(m)O(m) 大小的空间来记录当前行的 ff 值。

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的63. Unique Paths II 不同路径 II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。