跳转至

63. 不同路径 II

力扣链接(中等)：https://leetcode.cn/problems/unique-paths-ii

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

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

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

测试用例保证答案小于等于 2 * 109。

示例 1：

img

Text Only
1
2
3
4
5
6
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

img

Text Only
1
2
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

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

个人题解

本题相较于「62. 不同路径」新增了障碍物，主要区别就是有障碍物的位置肯定不可达，即无任何路径，那么显然应该 dp[i][j] = 0，由于存在下列递推关系，后续经过该位置的路径也不可行。

  1. 确定 dp 数组含义：dp[i][j] 表示从 [0, 0] 出发到 [i, j] 有多少条路径；
  2. 确定递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；
  3. dp 数组初始化：从 [0, 0] 出发到 [0/i, j/0] 均只有一条路径，因为机器人只能向右/下移动；
  4. 确定遍历顺序：由递推公式可见，逐层从左到右遍历；
  5. 推导 dp 数组：手动推导，结果合理。
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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        const int N = 110;

        const int _m = obstacleGrid.size();
        const int _n = obstacleGrid[0].size();
        int dp[N][N] = {};
        // memset(dp, 0, sizeof(dp));

        // 如果遇到障碍物，保留初始化零值，代表当前位置不可达
        for(int i = 0; i < _m && !obstacleGrid[i][0]; i++) dp[i][0] = 1;
        for(int j = 0; j < _n && !obstacleGrid[0][j]; j++) dp[0][j] = 1;

        for(int i = 1; i < _m; i++) {
            for(int j = 1; j < _n; j++) {
                if(obstacleGrid[i][j]) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[_m - 1][_n - 1];
    }
};