leetCode 62.不同路径 动态规划 + 空间复杂度优化

62. 不同路径 - 力扣(LeetCode)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

>>动态规划

机器人从(0,0)位置出发,到(m-1,n-1)终点

按照动规五部曲分析:

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],也就是说 dp[i][j] = dp[i-1][j] + dp[i][j-1];

3.dp数组的初始化

dp[i][0]一定都是1,因为从(0,0)的位置到(i,0)的路径只有一条;

dp[0][j]一定也都是1,因为从(0,0)的位置到(0,j)的路径只有一条

初始化代码为:

for(int i = 0,i < m;i++) dp[i][0] = 1;
for(int j = 0;j < n;j++) dp[0][j] = 1;

4.确定遍历顺序

dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导出来,那么从左到右一层一层遍历就可以了。可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的

5.举例推导dp数组

class Solution {
public:// 动态规划 时间复杂度:O(m x n) 空间复杂度:O(m x n)int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,0));for(int i=0;i<m;i++) dp[i][0] = 1;for(int j=0;j<n;j++) dp[0][j] = 1;for(int i=1;i<m;i++) {for(int j=1;j<n;j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};
  • 时间复杂度:O(m * n)
  • 空间复杂度:O(m * n)

其实用一个一维数组(也可以理解是滚动数组)也可以,只是不利于理解,但可以优化空间,建议先理解了二维,再理解一维

class Solution {
public:// 动态规划 时间复杂度:O(m x n) 空间复杂度:O(n)int uniquePaths(int m,int n) {vector<int> dp(n);for(int j = 0;j < n;j++) dp[j] = 1;for(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {dp[j] += dp[j-1];}}return dp[n-1];}
};
  • 时间复杂度:O(m * n)
  • 空间复杂度:O(n)

 

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

参考和推荐文章、视频:

 代码随想录 (programmercarl.com)

 动态规划中如何初始化很重要!| LeetCode:62.不同路径_哔哩哔哩_bilibili

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/144130.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大数据之Flume

Flume概述 一个高可用&#xff08;稳定&#xff09;&#xff0c;高可靠&#xff08;稳定&#xff09;&#xff0c;分布式的海量日志采集&#xff0c;聚合和传输的系统。Flume基于流式架构&#xff0c;灵活简单。日志文件即txt文件&#xff0c;不能传输音频&#xff0c;视频&am…

194、SpringBoot -- 下载和安装 Erlang 、 RabbitMQ

本节要点&#xff1a; 一些命令&#xff1a; 小黑窗输入&#xff1a; rabbitmq-plugins enable rabbitmq_management 启动控制台插件 rabbitmq-server 启动rabbitMQ服务器 管理员启动小黑窗&#xff1a; rabbitmq-service install 添加rabbitMQ为本地服务 启动浏览器访问 ht…

stl格式-3D三角形

文章目录 什么是stl文件?格式首选stl的语法1.这是一个stl格式的文件:(ASCII码)2.下面先举个例子(难度略微提示)补充:关于\<\<我试了一下:这个法线你随便写好像也没问题\>> 3.来个立方体4.最后再写一个由三个直角形组成的立方体(直棱锥)5.amend 修正(右手定则,法线…

如何定时备份使用Docker构建的MySQL容器中的数据库

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…

单目标应用:基于螳螂搜索算法(Mantis Search Algorithm,MSA)的微电网优化调度MATLAB

一、螳螂搜索算法 螳螂搜索算法&#xff08;Mantis Search Algorithm&#xff0c;MSA&#xff09;由Mohamed Abdel-Basset等人于2023年提出&#xff0c;该算法模拟螳螂独特的狩猎和性同类相食行为。MSA由三个优化阶段组成&#xff0c;包括寻找猎物&#xff08;探索&#xff09…

OpenHarmony自定义组件介绍

一、创建自定义组件 在ArkUI中&#xff0c;UI显示的内容均为组件&#xff0c;由框架直接提供的称为系统组件&#xff0c;由开发者定义的称为自定义组件。在进行 UI 界面开发时&#xff0c;通常不是简单的将系统组件进行组合使用&#xff0c;而是需要考虑代码可复用性、业务逻辑…

Windows 下安装和配置 Redis (详细图文)

目录 下载 Redis安装 Redis配置 Redis修改密码(可选)配置环境变量注册系统服务 Redis 桌面管理工具附&#xff1a;开源项目微服务商城项目前后端分离项目 下载 Redis 访问 Redis 下载地址&#xff1a;https://github.com/tporadowski/redis/releases 下载 Redis 时&#xff0c…

Golang的测试、基准测试和持续集成

在Golang中&#xff0c;内置的垃圾回收器处理内存管理&#xff0c;自动执行内存分配和释放。 单元测试是软件开发中至关重要的一个方面&#xff0c;它确保了代码的正确性并在开发过程中尽早发现错误。在Go中&#xff0c;编写有效的单元测试非常简单&#xff0c;并为开发人员提…

Bee2.1.8支持Spring Boot 3.0.11,active命令行选择多环境,多表查改增删(bee-spring-boot发布,更新maven)

天下大势&#xff0c;分久必合&#xff01; Hibernate/MyBatis plus Sharding JDBC Jpa Spring data GraphQL App ORM (Android, 鸿蒙) Bee Spring Cloud 微服务使用数据库更方便&#xff1a;Bee Spring Boot; 轻松支持多数据源&#xff0c;Sharding, Mongodb. 要整合一堆的…

【Java 进阶篇】深入理解 SQL 聚合函数

在 SQL 数据库中&#xff0c;聚合函数是一组强大的工具&#xff0c;用于处理和分析数据。它们可以帮助您对数据进行统计、计算总和、平均值、最大值、最小值等操作。无论您是数据库开发者、数据分析师还是希望更好地了解 SQL 数据库的用户&#xff0c;了解聚合函数都是非常重要…

【算法练习Day8】 kmp算法找出字符串中第一个匹配项的下标反转字符串中的单词重复的子字符串

、​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;练题 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录 kmp算法找出字符串中第…

ubuntu18.04 OpenGL开发(显示YUV)

源码参考&#xff1a;https://download.csdn.net/download/weixin_55163060/88382816 安装opengl库 sudo apt install libglu1-mesa-dev freeglut3-dev mesa-common-dev 安装opengl工具包 sudo apt install mesa-utils 检查opengl版本信息&#xff08;桌面终端执行&#xff09…

UWB技术在汽车智能制造的应用

返修区车辆管理项目 应用背景 在车辆总装生产线中&#xff0c;车辆下线后检测与返修是最后一个关键环节&#xff0c;整车一旦下线&#xff0c;由于流水线装配工艺、来料等原因&#xff0c;可能会出现部分整车存在瑕疵&#xff0c;进而进入返修区域待检。由于可能出现问题的不确…

【EI会议征稿】第三届机械、建模与材料工程国际学术会议(I3ME 2023)

第三届机械、建模与材料工程国际学术会议&#xff08;I3ME 2023&#xff09; 2023 3rd International Conference on Mechanical, Modeling and Materials Engineering 第三届机械、建模与材料工程国际学术会议&#xff08;I3ME 2023&#xff09;将于2023年12月1-3日在中国长春…

五子棋AI算法和开局定式(直指13式)破解

五子棋AI算法和开局定式&#xff08; 直指13式 &#xff09;破解 先前发了几篇五子棋游戏程序设计的博文&#xff0c;设计了游戏程序&#xff0c;也设计了AI智能奕棋的算法&#xff0c;运行程序检测算法的可行性&#xff0c;完成人机模式游戏功能的设置。这还不够&#xff0c;…

十六.镜头知识之工业镜头的质量判断因素

十六.镜头知识之工业镜头的质量判断因素 文章目录 十六.镜头知识之工业镜头的质量判断因素1.分辨率(Resolution)2.明锐度(Acutance)3.景深(DOF)&#xff1a;4. 最大相对孔径与光圈系数5.工业镜头各参数间的相互影响关系5.1.焦距大小的影响情况5.2.光圈大小的影响情况5.3.像场中…

WebPack5进阶使用总结(二)

WebPack5进阶使用总结 1、处理js资源1.1、Eslint1.2、在webpack中使用Eslint1.3、Babel1.4、在webpack中使用 2、处理HTML资源3、开发服务器&自动化4、生产模式介绍5、Css处理5.1、Css兼容性处理5.2、合并配置5.3、Css压缩 配套视频&#xff1a;尚硅谷Webpack5入门到原理 配…

STM32H7系列MPU与CACHE以及RAM

一、启用cache 启用cache很简单&#xff0c;就是这两句&#xff0c;分别打开I-Cache和D-Cache&#xff0c;但是如果只使用这两句&#xff0c;再操作DMA和FLASH时就很有可能遇到问题&#xff0c;后面会具体说明。 SCB_EnableICache();//使能I-CacheSCB_EnableDCache();//使能D-…

Android studio “Layout Inspector“工具在Android14 userdebug设备无法正常使用

背景描述 做rom开发的都知道&#xff0c;“Layout Inspector”和“Attach Debugger to Android Process”是studio里很好用的工具&#xff0c;可以用来查看布局、调试系统进程&#xff08;比如setting、launcher、systemui&#xff09;。 问题描述 最进刚开始一个Android 14…

现代数据架构-湖仓一体

当前的数据架构已经从数据库、数据仓库&#xff0c;发展到了数据湖、湖仓一体架构&#xff0c;本篇文章从头梳理了一下数据行业发展的脉络。 上世纪&#xff0c;最早出现了关系型数据库&#xff0c;也就是DBMS&#xff0c;有商业的Oracle、 IBM的DB2、Sybase、Informix、 微软…