【LetMeFly】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：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] 为 0 或 1
解题方法：动态规划
直接使用原来的obstacleGrid数组，令obstacleGrid[i][j]代表走到(i, j)为止的总方案数。
因为是原地修改，所以就要求我们从左到右从上到下按顺序遍历。
遍历到一个元素时：
- 如果这个元素为
1，就说明这里是障碍，走这里的方案数为0；
- 否则，走这里的方案数为“由上面来”和“由左边来”的方案数之和（若不可由上而来则将“由上面来”的方案数记为1）。
特别的，对于起始位置obstacleGrid[0][0]：
- 若初始值为
1说明不可从这里出发，总方案数为0；
- 若初始值为
0说明可以从这里出发，令obstacleGrid[0][0] = 1。
时空复杂度分析
- 时间复杂度$O(size(obstacleGrid))$
- 空间复杂度$O(1)$
AC代码
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| '''
Author: LetMeFly
Date: 2025-02-08 09:55:16
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-08 09:58:42
'''
from typing import List
class Solution:
def uniquePathsWithObstacles(self, a: List[List[int]]) -> int:
a[0][0] = 0 if a[0][0] else 1
for i in range(len(a)):
for j in range(len(a[0])):
if a[i][j] != 0 and (i or j):
a[i][j] = 0
continue
if i > 0:
a[i][j] += a[i - 1][j]
if j > 0:
a[i][j] += a[i][j - 1]
return a[-1][-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
26
27
28
29
|
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
for (int i = 0; i < obstacleGrid.size(); i++) {
for (int j = 0; j < obstacleGrid[0].size(); j++) {
if (i == 0 && j == 0) {
obstacleGrid[i][j] = obstacleGrid[i][j] ? 0 : 1;
continue;
} else if (obstacleGrid[i][j]) {
obstacleGrid[i][j] = -1;
continue;
}
if (i > 0 && obstacleGrid[i - 1][j] != -1) {
obstacleGrid[i][j] += obstacleGrid[i - 1][j];
}
if (j > 0 && obstacleGrid[i][j - 1] != -1) {
obstacleGrid[i][j] += obstacleGrid[i][j - 1];
}
}
}
return max(obstacleGrid.back().back(), 0);
}
};
|
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
25
26
27
28
29
|
class Solution {
public int uniquePathsWithObstacles(int[][] a) {
if (a[0][0] == 1) {
return 0;
}
a[0][0] = 1;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if (a[i][j] == 1 && i + j > 0) {
a[i][j] = 0;
continue;
}
if (i > 0) {
a[i][j] += a[i - 1][j];
}
if (j > 0) {
a[i][j] += a[i][j - 1];
}
}
}
return a[a.length - 1][a[0].length - 1];
}
}
|
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
28
29
|
package main
func uniquePathsWithObstacles(a [][]int) int {
if a[0][0] == 1 {
return 0
}
a[0][0] = 1
for i := range a {
for j := range a[0] {
if a[i][j] == 1 && i + j > 0 {
a[i][j] = 0
continue
}
if i > 0 {
a[i][j] += a[i - 1][j]
}
if j > 0 {
a[i][j] += a[i][j - 1]
}
}
}
return a[len(a) - 1][len(a[0]) - 1]
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
Tisfy：https://letmefly.blog.csdn.net/article/details/145509662