力扣00063.不同路径 II

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 10 分钟
不同路径 II、数组、动态规划、矩阵、中等

题目描述

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

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

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

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

示例 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

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1; i < m; ++i) {
            dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i-1][0] : 0;
        }
        for (int j = 1; j < n; ++j) {
            dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j-1] : 0;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return dp[m-1][n-1];
    }
};

结果

执行用时 : 3 ms, 击败 61.23% 使用 C++ 的用户

内存消耗 : 9.98 MB, 击败 24.67% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1; i < m; ++i) {
            dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i - 1][0] : 0;
        }
        for (int j = 1; j < n; ++j) {
            dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 40.91 MB, 击败 5.02% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] if obstacleGrid[i][0] == 0 else 0
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] if obstacleGrid[0][j] == 0 else 0
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                else:
                    dp[i][j] = 0
        return dp[-1][-1]

结果

执行用时 : 10 ms, 击败 95.03% 使用 Python 的用户

内存消耗 : 11.41 MB, 击败 90.60% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] if obstacleGrid[i][0] == 0 else 0
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] if obstacleGrid[0][j] == 0 else 0
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                else:
                    dp[i][j] = 0
        return dp[-1][-1]

结果

执行用时 : 26 ms, 击败 99.27% 使用 Python3 的用户

内存消耗 : 16.46 MB, 击败 60.61% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {
    int m = obstacleGridSize;
    int n = obstacleGridColSize[0];
    int dp[m][n];
    dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
    for (int i = 1; i < m; ++i) {
        dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i - 1][0] : 0;
    }
    for (int j = 1; j < n; ++j) {
        dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[m - 1][n - 1];
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 C 的用户

内存消耗 : 5.82 MB, 击败 78.57% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;
        int[,] dp = new int[m, n];
        dp[0, 0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1; i < m; ++i) {
            dp[i, 0] = obstacleGrid[i][0] == 0 ? dp[i - 1, 0] : 0;
        }
        for (int j = 1; j < n; ++j) {
            dp[0, j] = obstacleGrid[0][j] == 0 ? dp[0, j - 1] : 0;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
                } else {
                    dp[i, j] = 0;
                }
            }
        }
        return dp[m - 1, n - 1];
    }
}

结果

执行用时 : 59 ms, 击败 79.63% 使用 C# 的用户

内存消耗 : 40.20 MB, 击败 46.91% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
    dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;
    for (let i = 1; i < m; ++i) {
        dp[i][0] = obstacleGrid[i][0] === 0 ? dp[i - 1][0] : 0;
    }
    for (let j = 1; j < n; ++j) {
        dp[0][j] = obstacleGrid[0][j] === 0 ? dp[0][j - 1] : 0;
    }
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            if (obstacleGrid[i][j] === 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[m - 1][n - 1];
};

结果

执行用时 : 57 ms, 击败 83.99% 使用 JavaScript 的用户

内存消耗 : 50.55 MB, 击败 10.73% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m: number = obstacleGrid.length;
    const n: number = obstacleGrid[0].length;
    const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
    dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;
    for (let i = 1; i < m; ++i) {
        dp[i][0] = obstacleGrid[i][0] === 0 ? dp[i - 1][0] : 0;
    }
    for (let j = 1; j < n; ++j) {
        dp[0][j] = obstacleGrid[0][j] === 0 ? dp[0][j - 1] : 0;
    }
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            if (obstacleGrid[i][j] === 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[m - 1][n - 1];
}

结果

执行用时 : 67 ms, 击败 62.72% 使用 TypeScript 的用户

内存消耗 : 52.36 MB, 击败 21.30% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($obstacleGrid) {
        $m = count($obstacleGrid);
        $n = count($obstacleGrid[0]);
        $dp = array_fill(0, $m, array_fill(0, $n, 0));
        $dp[0][0] = $obstacleGrid[0][0] === 0 ? 1 : 0;
        for ($i = 1; $i < $m; ++$i) {
            $dp[$i][0] = $obstacleGrid[$i][0] === 0 ? $dp[$i - 1][0] : 0;
        }
        for ($j = 1; $j < $n; ++$j) {
            $dp[0][$j] = $obstacleGrid[0][$j] === 0 ? $dp[0][$j - 1] : 0;
        }
        for ($i = 1; $i < $m; ++$i) {
            for ($j = 1; $j < $n; ++$j) {
                if ($obstacleGrid[$i][$j] === 0) {
                    $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
                } else {
                    $dp[$i][$j] = 0;
                }
            }
        }
        return $dp[$m - 1][$n - 1];
    }
}

结果

执行用时 : 13 ms, 击败 14.29% 使用 PHP 的用户

内存消耗 : 20.22 MB, 击败 14.29% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
        let m = obstacleGrid.count
        let n = obstacleGrid[0].count
        var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0
        for i in 1..<m {
            dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i - 1][0] : 0
        }
        for j in 1..<n {
            dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0
        }
        for i in 1..<m {
            for j in 1..<n {
                if obstacleGrid[i][j] == 0 {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                } else {
                    dp[i][j] = 0
                }
            }
        }
        return dp[m - 1][n - 1]
    }
}

结果

执行用时 : 4 ms, 击败 92.41% 使用 Swift 的用户

内存消耗 : 15.29 MB, 击败 40.51% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        val dp = Array(m) { IntArray(n) }
        dp[0][0] = if (obstacleGrid[0][0] == 0) 1 else 0
        for (i in 1 until m) {
            dp[i][0] = if (obstacleGrid[i][0] == 0) dp[i - 1][0] else 0
        }
        for (j in 1 until n) {
            dp[0][j] = if (obstacleGrid[0][j] == 0) dp[0][j - 1] else 0
        }
        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = if (obstacleGrid[i][j] == 0) {
                    dp[i - 1][j] + dp[i][j - 1]
                } else {
                    0
                }
            }
        }
        return dp[m - 1][n - 1]
    }
}

结果

执行用时 : 145 ms, 击败 89.29% 使用 Kotlin 的用户

内存消耗 : 34.70 MB, 击败 100.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  int uniquePathsWithObstacles(List<List<int>> obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    List<List<int>> dp = List.generate(m, (index) => List<int>.filled(n, 0));
    dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
    for (int i = 1; i < m; ++i) {
      dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i - 1][0] : 0;
    }
    for (int j = 1; j < n; ++j) {
      dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0;
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        if (obstacleGrid[i][j] == 0) {
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        } else {
          dp[i][j] = 0;
        }
      }
    }
    return dp[m - 1][n - 1];
  }
}

结果

执行用时 : 281 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 148.41 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[0][0] = 1 - obstacleGrid[0][0]
    for i := 1; i < m; i++ {
        if obstacleGrid[i][0] == 0 {
            dp[i][0] = dp[i-1][0]
        }
    }
    for j := 1; j < n; j++ {
        if obstacleGrid[0][j] == 0 {
            dp[0][j] = dp[0][j-1]
        }
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 0 {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
}

结果

执行用时 : 1 ms, 击败 34.05% 使用 Go 的用户

内存消耗 : 2.28 MB, 击败 29.77% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# @param {Integer[][]} obstacle_grid
# @return {Integer}
def unique_paths_with_obstacles(obstacle_grid)
    m = obstacle_grid.length
    n = obstacle_grid[0].length
    dp = Array.new(m) { Array.new(n, 0) }
    dp[0][0] = 1 - obstacle_grid[0][0]
    (1...m).each do |i|
        dp[i][0] = dp[i-1][0] if obstacle_grid[i][0] == 0
    end
    (1...n).each do |j|
        dp[0][j] = dp[0][j-1] if obstacle_grid[0][j] == 0
    end
    (1...m).each do |i|
        (1...n).each do |j|
            dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacle_grid[i][j] == 0
        end
    end
    dp[m-1][n-1]
end

结果

执行用时 : 35 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.51 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object Solution {
  def uniquePathsWithObstacles(obstacleGrid: Array[Array[Int]]): Int = {
    val m = obstacleGrid.length
    val n = obstacleGrid(0).length
    val dp = Array.ofDim[Int](m, n)
    dp(0)(0) = 1 - obstacleGrid(0)(0)
    for (i <- 1 until m) {
      dp(i)(0) = if (obstacleGrid(i)(0) == 0) dp(i-1)(0) else 0
    }
    for (j <- 1 until n) {
      dp(0)(j) = if (obstacleGrid(0)(j) == 0) dp(0)(j-1) else 0
    }
    for (i <- 1 until m) {
      for (j <- 1 until n) {
        dp(i)(j) = if (obstacleGrid(i)(j) == 0) dp(i-1)(j) + dp(i)(j-1) else 0
      }
    }
    dp(m-1)(n-1)
  }
}

结果

执行用时 : 582 ms, 击败 -% 使用 Scala 的用户

内存消耗 : 56.59 MB, 击败 -% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
impl Solution {
    pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
        let m = obstacle_grid.len();
        let n = obstacle_grid[0].len();
        let mut dp = vec![vec![0; n]; m];
        dp[0][0] = 1 - obstacle_grid[0][0];
        for i in 1..m {
            dp[i][0] = if obstacle_grid[i][0] == 0 { dp[i - 1][0] } else { 0 };
        }
        for j in 1..n {
            dp[0][j] = if obstacle_grid[0][j] == 0 { dp[0][j - 1] } else { 0 };
        }
        for i in 1..m {
            for j in 1..n {
                dp[i][j] = if obstacle_grid[i][j] == 0 {
                    dp[i - 1][j] + dp[i][j - 1]
                } else {
                    0
                };
            }
        }
        dp[m - 1][n - 1]
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.09 MB, 击败 50.00% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户