152 - 63 不同路径2

题目

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

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

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

img

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

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

示例 1:

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

1. 向右 -> 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右 -> 向右

解答

动态规划的推导公式是一样的，当前路径数量=上面格子路径数量+左边格子路径数量。两条初始边都是1。

如果数组原来是0，那么就用公式，如果是1，那么就把它变成0，因为没有路可以到那里。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or obstacleGrid[0][0] == 1:
            return 0
        row = len(obstacleGrid)
        col = len(obstacleGrid[0])
        obstacleGrid[0][0] = 1
        for i in range(1, col):
            if obstacleGrid[0][i] == 1:
                obstacleGrid[0][i] = 0
            else:
                obstacleGrid[0][i] = obstacleGrid[0][i-1]
        for i in range(1, row):
            if obstacleGrid[i][0] == 1:
                obstacleGrid[i][0] = 0
            else:
                obstacleGrid[i][0] = obstacleGrid[i-1][0]

        for i in range(1, row):
            for j in range(1, col):
                if obstacleGrid[i][j] == 0:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + \
                        obstacleGrid[i][j-1]
                else:
                    obstacleGrid[i][j] = 0
        return obstacleGrid[-1][-1]

Runtime: 40 ms, faster than 98.50% of Python3 online submissions for Unique Paths II.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Unique Paths II.

var uniquePathsWithObstacles = function(obstacleGrid) {
  if (!obstacleGrid || obstacleGrid[0][0] === 1) {
    return 0
  }
  row = obstacleGrid.length
  col = obstacleGrid[0].length
  obstacleGrid[0][0] = 1
  for (let i = 1; i < row; i++) {
    if (obstacleGrid[i][0] === 1) {
      obstacleGrid[i][0] = 0
    } else {
      obstacleGrid[i][0] = obstacleGrid[i - 1][0]
    }
  }
  for (let i = 1; i < col; i++) {
    if (obstacleGrid[0][i] === 1) {
      obstacleGrid[0][i] = 0
    } else {
      obstacleGrid[0][i] = obstacleGrid[0][i - 1]
    }
  }
  for (let i = 1; i < row; i++) {
    for (let j = 1; j < col; j++) {
      if (obstacleGrid[i][j] === 1) {
        obstacleGrid[i][j] = 0
      } else {
        obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
      }
    }
  }
  return obstacleGrid[row - 1][col - 1]
};

Runtime: 52 ms, faster than 95.23% of JavaScript online submissions for Unique Paths II.

Memory Usage: 35.4 MB, less than 100.00% of JavaScript online submissions for Unique Paths II.

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    if obstacleGrid == nil || obstacleGrid[0][0] == 1 {
        return 0
    }
    obstacleGrid[0][0] = 1
    row := len(obstacleGrid)
    col := len(obstacleGrid[0])
    for i := 1; i < row; i++ {
        if obstacleGrid[i][0] == 1 {
            obstacleGrid[i][0] = 0
        } else {
            obstacleGrid[i][0] = obstacleGrid[i-1][0]
        }
    }
    for i := 1; i < col; i++ {
        if obstacleGrid[0][i] == 1 {
            obstacleGrid[0][i] = 0
        } else {
            obstacleGrid[0][i] = obstacleGrid[0][i-1]
        }
    }

    for i := 1; i < row; i++ {
        for j := 1; j < col; j++ {
            if obstacleGrid[i][j] == 1 {
                obstacleGrid[i][j] = 0
            } else {
                obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
            }
        }
    }
    return obstacleGrid[row-1][col-1]
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Unique Paths II.

Memory Usage: 2.6 MB, less than 100.00% of Go online submissions for Unique Paths II.