leetCode 63.不同路径II 动态规划 + 空间复杂度优化 一维dp

news/2024/11/4 13:06:46/

63. 不同路径 II - 力扣(LeetCode)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2:

输入:obstacleGrid = [[0,1],[0,0]]
输出:1

>>思路

相比这道leetCode 62.不同路径就有了障碍~,其实在有障碍的时候,就是标记对应的dp数组 保持初始值(0)即可!!!

>>动规五部曲

1.确定dp数组(dp table)以及下标的含义

dp[i][j]:表示从(0,0)出发,到(i,j)有dp[i][j]条不同的路径

2.确定递推公式

  • 在不是障碍的时候,dp[i][j] = dp[i-1][j] + dp[i][j-1];
  • 在是障碍的时候,那么(i,j)就保持初始状态(初始状态为0)
if(obstacleGrid[i][j] == 0) { // 当(i,j)没有障碍的时候,再推导dp[i][j]dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}

3.dp数组初始化

vector<vector<int>> dp(m,vector<int>(n,0));//初始值为0
for(int i = 0;i < m;i++) dp[i][0] = 1;
for(int j = 0;j < n;j++) dp[0][j] = 1;
  • 因为从(0,0)的位置到(i,0)的路径一条,即dp[i][0]一定为1;
  • 因为从(0,0)的位置到(0,j)的路径一条,即dp[0][j]一定为1;

但如果(i,0)这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置,那障碍之后的dp[i][0]就应是初始值0 

vector<vector<int>> dp(m,vector<int>(n,0));//初始值为0
for(int i = 0;i < m && obstacleGrid[i][0] == 0;i++) dp[i][0] = 1;
for(int j = 0;j < n && obstacleGrid[0][j] == 0;j++) dp[0][j] = 1;

注意for循环的终止条件:

  • ① 遇到obstacleGrid[i][0] == 1终止dp[i][0]的赋值1的操作
  • ② 遇到obstacleGrid[0][j] == 1终止dp[0][j]的赋值1的操作

4.确定遍历顺序

从递推公式dp[i][j] = dp[i-1][j] + dp[i][j-1] 中可以看出,一定是从左到右一层一层遍历,可以保证推导dp[i][j]的时候,dp[i-1][j] 和 dp[i][j-1]一定是有数值的

for(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {if(obstacleGrid[i][j]  == 1) continue;dp[i][j] = dp[i-1][j] + dp[i][j-1];}
}

5.举例推导dp数组

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍,直接返回0return 0;vector<vector<int>> dp(m,vector<int>(n,0));for(int i=0;i<m && obstacleGrid[i][0] == 0;i++) dp[i][0] = 1;for(int j=0;j<n && obstacleGrid[0][j] == 0;j++) dp[0][j] = 1;for(int i=1;i<m;i++) {  for(int j=1;j<n;j++) {if(obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};// 时间复杂度:O(m x n) m、n分别为 obstacleGrid 的宽度和长度
// 空间复杂度:O(m x n)
  • 时间复杂度:O(m x n) m、n分别为 obstacleGrid 的宽度和长度
  • 空间复杂度:O(m x n)

进一步空间优化:

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid[0][0] == 1) return 0;int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<int> dp(n);for(int j = 0;j < n;j++) {if(obstacleGrid[0][j] == 1)dp[j] = 0;else if(j == 0)dp[j] = 1;elsedp[j] = dp[j-1];}for(int i = 1;i < m;++i) {for(int j = 0;j < n;++j) {if(obstacleGrid[i][j] == 1) dp[j] = 0;else if(j!=0) dp[j] = dp[j] + dp[j-1];}}return dp.back();}// 时间复杂度:O(m x n) m、n分别为 obstacleGrid 的宽度和长度// 空间复杂度:O(n)
};
  • 时间复杂度:O(m x n) m、n分别为 obstacleGrid 的宽度和长度
  • 空间复杂度:O(n) 

来自代码随想录的课堂截图:

参考和推荐文章、视频:

动态规划,这次遇到障碍了| LeetCode:63. 不同路径 II_哔哩哔哩_bilibili

 代码随想录 (programmercarl.com)

我的往期文章: leetCode 62.不同路径 动态规划 + 空间复杂度优化_呵呵哒( ̄▽ ̄)"的博客-CSDN博客


http://www.ppmy.cn/news/1128213.html

相关文章

对标8155体验,降本20%以上!这家企业用“量产”证明

智能座舱逐渐成为智能汽车标配。 根据高工智能汽车研究院监测的数据显示&#xff0c;2022年中国市场&#xff08;不含进出口&#xff09;乘用车搭载智能数字座舱&#xff08;大屏语音车联网OTA&#xff09;前装标配交付795.05万辆&#xff0c;同比增长40.59%&#xff0c;前装搭…

oracle分组合并数值带顺序

比如&#xff1a;有如下一张设备电子围栏位置坐标的表&#xff08;tb_equ_point&#xff09;。 equ_name:设备电子围栏名称 point_id:点位坐标id point_x:点位x坐标 point_y:点位y坐标。 附数据&#xff1a; INSERT INTO "tb_equ_point" ("EQU_NAME",…

codesys【虚轴】

1概述&#xff1a;codesys里有3个轴&#xff1a; 自由编码器&#xff0c;虚轴&#xff0c;实轴。 流程&#xff1a;【高速输入&#xff1a;采集AB脉冲】带》【自由编码器】带》【虚轴】带》【实轴】 1虚轴&#xff1a; 用法和实轴一样。 一般用于&#xff0c;一拖多。 2编…

MySQL 的 C 语言接口

1. mysql_init MYSQL *mysql_init(MYSQL *mysql); mysql_init函数的作用&#xff1a;创建一个 MYSQL 对象&#xff08;该对象用于连接数据库&#xff09;。 mysql_init函数的参数&#xff1a; ① mysql&#xff1a;MYSQL 结构体指针&#xff0c;一般设置为 NULL 。 mysql_init函…

基于Matlab实现全局优化算法

Matlab是一种非常强大的数学建模和计算工具&#xff0c;它提供了许多优化算法的实现。全局优化算法是一种能够找到全局最优解的优化算法&#xff0c;相对于局部优化算法来说&#xff0c;具有更强的全局搜索能力。在本文中&#xff0c;我们将介绍如何使用Matlab实现全局优化算法…

Nginx代理victoriametrics集群配置

1,首先安装nginx yum install -y nginx 2,生成密钥文件 安装htpasswd工具 yum install -y httpd-tools 生成密钥文件,prometheus为用户名 htpasswd -c /etc/nginx/conf.d/passwd prometheus 3,修改nginx配置文件nginx.conf,增加如下内容 upstream vmselect {server 10.…

SQL Server 统计后台sql语句执行情况

SELECT TOP 100 qs.total_worker_time/1000 AS [总消耗CPU 时间(ms)], qs.execution_count [运行次数], qs.total_worker_time / qs.execution_count / 1000 AS [平均消耗CPU 时间(ms)], last_execution_ti…

hive3.X的HiveServer2 内存泄漏问题定位与优化方案(bug)

参考文档&#xff1a; https://juejin.cn/post/7141331245627080735?searchId20230920140418F85636A0735C03971F71 官网社区&#xff1a; https://issues.apache.org/jira/browse/HIVE-22275 In the case that multiple statements are run by a single Session before bein…