不同路径 II

63. 不同路径 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

相似题目

不同路径

不同路径 III

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { } };

python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-15 14:43:17

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

golang 解法, 执行用时: 4 ms, 内存消耗: 2.3 MB, 提交时间: 2023-09-15 14:41:51

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    n, m := len(obstacleGrid), len(obstacleGrid[0])
    f := make([]int, m)
    if obstacleGrid[0][0] == 0 {
        f[0] = 1
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if obstacleGrid[i][j] == 1 {
                f[j] = 0
                continue
            }
            if j - 1 >= 0 && obstacleGrid[i][j-1] == 0 {
                f[j] += f[j-1]
            }
        }
    }
    return f[len(f)-1]
}

java 解法, 执行用时: 0 ms, 内存消耗: 39.5 MB, 提交时间: 2023-09-15 14:41:09

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];

        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }
        
        return f[m - 1];
    }
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 8 MB, 提交时间: 2023-09-15 14:40:44

/**
 * 我们用 f(i,j) 来表示从坐标 (0,0) 到坐标 (i,j) 的路径总数，
 * u(i,j) 表示坐标 (i,j) 是否可行，如果坐标 (i,j) 有障碍物，u(i,j)=0，否则 u(i,j)=1。
 */
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
        vector <int> f(m);

        f[0] = (obstacleGrid[0][0] == 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f.back();
    }
};

php 解法, 执行用时: 8 ms, 内存消耗: 15.7 MB, 提交时间: 2021-07-30 16:00:27

class Solution {

    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($grid) {
        $n = count($grid);
        $m = count($grid[0]);
        $f = array_fill(0, $m, 0);
        if ( $grid[0][0] == 0 ) {
            $f[0] = 1;
        }
        for ( $i = 0; $i < $n; $i++ ) {
            for ( $j = 0; $j < $m; $j++ ) {
                if ( $grid[$i][$j] == 1 ) {
                    $f[$j] = 0;
                    continue;
                }
                if ( $j > 0 && $grid[$i][$j-1] == 0 ) $f[$j] += $f[$j-1];
            }
        }
        return $f[$m-1];
    }
}

上一题

下一题

详情