当前位置：首页 > news >正文

LeetCode 0063.不同路径 II：动态规划 - 原地使用地图数组，几乎无额外空间开销

news 2025/6/30 17:22:31

【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 * 10⁹。

示例 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

解题方法：动态规划

直接使用原来的obstacleGrid数组，令obstacleGrid[i][j]代表走到(i, j)为止的总方案数。

因为是原地修改，所以就要求我们从左到右从上到下按顺序遍历。

遍历到一个元素时：

如果这个元素为1，就说明这里是障碍，走这里的方案数为0；
否则，走这里的方案数为“由上面来”和“由左边来”的方案数之和（若不可由上而来则将“由上面来”的方案数记为1）。

特别的，对于起始位置obstacleGrid[0][0]：

若初始值为1说明不可从这里出发，总方案数为0；
若初始值为0说明可以从这里出发，令obstacleGrid[0][0] = 1。

时空复杂度分析

时间复杂度 $O (s i ze (o b s t a c l e G r i d))$
空间复杂度 $O (1)$

AC代码

Python

'''
Author: LetMeFly
Date: 2025-02-08 09:55:16
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-08 09:58:42
'''
from typing import Listclass Solution:def uniquePathsWithObstacles(self, a: List[List[int]]) -> int:a[0][0] = 0 if a[0][0] else 1for i in range(len(a)):for j in range(len(a[0])):if a[i][j] != 0 and (i or j):a[i][j] = 0continueif i > 0:a[i][j] += a[i - 1][j]if j > 0:a[i][j] += a[i][j - 1]return a[-1][-1]

C++

/** @Author: LetMeFly* @Date: 2025-02-08 09:36:16* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-08 09:53:50*/
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

/** @Author: LetMeFly* @Date: 2025-02-08 09:55:20* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-08 10:02:07*/
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

/** @Author: LetMeFly* @Date: 2025-02-08 09:55:29* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-08 10:04:49*/
package mainfunc uniquePathsWithObstacles(a [][]int) int {if a[0][0] == 1 {return 0}a[0][0] = 1for i := range a {for j := range a[0] {if a[i][j] == 1 && i + j > 0 {a[i][j] = 0continue}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]
}