Skip to content

Latest commit

 

History

History
175 lines (138 loc) · 6.04 KB

0063.md

File metadata and controls

175 lines (138 loc) · 6.04 KB
title description keywords
63. 不同路径 II
LeetCode 63. 不同路径 II题解,Unique Paths II,包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
63. 不同路径 II
不同路径 II
Unique Paths II
解题思路
数组
动态规划
矩阵

63. 不同路径 II

🟠 Medium  🔖  数组 动态规划 矩阵  🔗 力扣 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

思路一:DP-压缩状态

复杂度分析

  • 时间复杂度: O(m * n),遍历整个二维数组。
  • 空间复杂度: O(m),使用了一个长度为 marr 数组来存储中间状态。

思路一:DP-压缩状态

复杂度分析

  • 时间复杂度: O(m * n),遍历整个二维数组。
  • 空间复杂度: O(1),由于obstacleGrid[i][j] 只与 obstacleGrid[i-1][j]obstacleGrid[i][j-1] 有关,所以可以直接原地修改 obstacleGrid 数组。

代码

::: code-tabs

@tab DP-压缩状态

// 时间复杂度 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];
};

@tab DP-更改原数组

// 时间复杂度 O(nm),空间复杂度 O(1)
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
	const m = obstacleGrid.length,
		n = obstacleGrid[0].length;

	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			// 遇到障碍物 obstacleGrid[i][j] 就变成 0
			if (obstacleGrid[i][j] == 1) {
				obstacleGrid[i][j] = 0;
				continue;
			}
			// 起点
			if (i == 0 && j == 0) {
				obstacleGrid[i][j] = 1;
			}
			// 第一行
			else if (i == 0) {
				obstacleGrid[i][j] = obstacleGrid[i][j - 1];
			}
			// 第一列
			else if (j == 0) {
				obstacleGrid[i][j] = obstacleGrid[i - 1][j];
			} else {
				obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
			}
		}
	}

	return obstacleGrid[m - 1][n - 1];
};

:::

相关题目

题号 标题 题解 标签 难度 力扣
62 不同路径 [✓] 数学 动态规划 组合数学 🟠 🀄️ 🔗
980 不同路径 III 位运算 数组 回溯 1+ 🔴 🀄️ 🔗
2304 网格中的最小路径代价 数组 动态规划 矩阵 🟠 🀄️ 🔗
2435 矩阵中和能被 K 整除的路径 数组 动态规划 矩阵 🔴 🀄️ 🔗