跳转至

63. 不同路径 II

难度：中等

题目

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 10^9。

示例 1：

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

输出：2

解释：3x3 网格的正中间有一个障碍物。

从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

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

输出：1

提示：

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

Reference

题解

从最后一行开始考虑，要到达右下角的方格，有两种方法：

  1. 从斜上方的方格开始，先向下后向右
  2. 从斜上方的方格开始，先向右后向下

使用\(f(i, j)\)记录从第\(i\)行第\(j\)列出发，到达终点的方案数。如果当前方格存在障碍，或者越界\(i\geq m, j\geq n\)，则无论如何都不能从当前方格到达终点，方案数\(f(i, j)\)为\(0\)。其余情况下，状态转移方程为

\[ f(i, j) = f(i + 1, j) + f(i, j + 1) \]
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        result = [[0] * n for _ in range(m)]
        result[m - 1][n - 1] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i < m - 1:
                    result[i][j] += result[i + 1][j]
                if j < n - 1:
                    result[i][j] += result[i][j + 1]
                if obstacleGrid[i][j]:
                    result[i][j] = 0
        return result[0][0]

可以将状态转移矩阵压缩到一维，减少空间复杂度：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        result = [0 for _ in range(n)]
        result[n - 1] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if j < n - 1:
                    result[j] += result[j + 1]
                if obstacleGrid[i][j]:
                    result[j] = 0
        return result[0]

评论