网站和域名都注册怎么连接成网址,做网站开视频网站,成都网站建设木子网络,义乌外贸公司联系方式【LetMeFly】63.不同路径 II#xff1a;动态规划 - 原地使用地图数组#xff0c;几乎无额外空间开销
力扣题目链接#xff1a;https://leetcode.cn/problems/unique-paths-ii/
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角#xff08;即 grid[0][0]#…【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 ( s i z e ( o b s t a c l e G r i d ) ) O(size(obstacleGrid)) O(size(obstacleGrid))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
Python Author: LetMeFly
Date: 2025-02-08 09:55:16
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-08 09:58:42from 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(vectorvectorint 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]
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ 千篇源码题解已开源 Tisfyhttps://letmefly.blog.csdn.net/article/details/145509662
