63. Unique Paths II

🟠   🔖  数组 动态规划 矩阵  🔗 LeetCode

题目

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output: 2

Explanation: There is one obstacle in the middle of the 3x3 grid above.

There are two ways to reach the bottom-right corner:

1. Right -> Right -> Down -> Down

2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]

Output: 1

Constraints:

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

题目大意

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

解题思路

• 这一题是 第 62 题 的加强版。也是一道考察 DP 的简单题。
• 这一题比第 62 题增加的条件是地图中会出现障碍物，障碍物的处理方法是 dp[i][j]=0。
• 需要注意的一种情况是，起点就是障碍物，那么这种情况直接输出 0 。

❤️	1	1	1	1	1	1
1	💩	1	2	💩	1	2
1	1	2	4	4	5	7

代码

// 时间复杂度 O(nm)，空间复杂度 O(m)
const path = (inputArr) => {
  // 如果起点就是障碍物
  if (inputArr[0][0] === 1) return 0;
  const m = inputArr.length;
  const n = inputArr[0].length;
  // 用0填充，因为现在有障碍物
  let arr = new Array(m).fill(0);
  // 第一列先写成1
  arr[0] = 1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (inputArr[j][i] === 1) {
        // 遇到障碍物arr[j]就变成0，这里包含了第一列的情况
        arr[j] = 0;
      } else if (j > 0) {
        arr[j] = arr[j - 1] + arr[j];
      }
    }
  }
  return arr[m - 1];
};

相关题目

相关题目

• 62. 不同路径
• 980. 不同路径 III
• 2304. 网格中的最小路径代价
• 2435. 矩阵中和能被 K 整除的路径

- [62. 不同路径](./0062.md)
- [980. 不同路径 III](https://leetcode.com/problems/unique-paths-iii)
- [2304. 网格中的最小路径代价](https://leetcode.com/problems/minimum-path-cost-in-a-grid)
- [2435. 矩阵中和能被 K 整除的路径](https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k)