代码随想录算法训练营第三十九天 | 62.不同路径,63. 不同路径 II
一、参考资料
不同路径
https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
视频讲解:https://www.bilibili.com/video/BV1ve4y1x7Eu
不同路径 II
https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html
视频讲解:https://www.bilibili.com/video/BV1Ld4y1k7c6
二、LeetCode62.不同路径
https://leetcode.cn/problems/unique-paths/description/
一个机器人位于一个 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
提示:
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9

class Solution {
public:int uniquePaths(int m, int n) {if (n <= 1) return 1;vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 1; i <= m; i++) dp[i][1] = 1;for (int j = 1; j <= n; j++) dp[1][j] = 1;for (int i = 2; i <= m; i++) {for (int j = 2; j <= n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m][n];}
};class Solution {
public:// 下标从0开始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];}
};进一步优化:
class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n);for (int i = 0; i < n; i++) dp[i] = 1;for (int j = 1; j < m; j++) {for (int i = 1; i < n; i++) {dp[i] += dp[i - 1];}}return dp[n - 1];}
};三、LeetCode63. 不同路径 II
https://leetcode.cn/problems/unique-paths-ii/description/
一个机器人位于一个 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
提示:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

//dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径
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) return 0;vector<vector<int>> dp(m, vector<int>(n));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];}
};空间优化版本:
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if (obstacleGrid[0][0] == 1)return 0;vector<int> dp(obstacleGrid[0].size());for (int j = 0; j < dp.size(); ++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 < obstacleGrid.size(); ++i)for (int j = 0; j < dp.size(); ++j){if (obstacleGrid[i][j] == 1)dp[j] = 0;else if (j != 0)dp[j] = dp[j] + dp[j-1];}return dp.back();}
};
相关文章:
代码随想录算法训练营第三十九天 | 62.不同路径,63. 不同路径 II
一、参考资料不同路径https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html 视频讲解:https://www.bilibili.com/video/BV1ve4y1x7Eu不同路径 IIhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://progr…...
数据库复习3
一. 简答题(共1题,100分) 1. (简答题) 存在数据库test,数据库中有如下表: 1.学生表 Student(Sno,Sname,Sage,Ssex) --Sno 学号,Sname 学生姓名,Sage 出生年月,Ssex 学生性别 主键Sno 2.教师表 Teacher(Tno,Tname) --T…...
顺序表的增删查改
数据结构 是数据存储的方式,对于不同的数据我们要采用不同的数据结构。就像交通运输,选用什么交通工具取决于你要运输的是人还是货物,以及它们的数量。 顺序存储结构 包括顺序表、链表、栈和队列等。 例如腾讯QQ中的好友列表,…...
jupyter matplotlib中文乱码解决
中文乱码可能有两种情况 1. matplotlib里面有中文字体 2. 没有中文字体 查看是否有中文字体: # 查询当前系统所有字体 from matplotlib.font_manager import FontManager import subprocessmpl_fonts = set(f.name for f in FontManager().ttflist)print(all font list get f…...
Smtplib之发邮件模块
目录 创建Smtp对象 Smtp类中的方法 MIME MIMEBase MIMEBase MIMEMultipart MIMEApplication MIMEAudio MIMEImage MIMEText 实例 texthtml格式 发送带图片附件的邮件 发送带附件的邮件 含多种格式 SMTP模块 SMTP 简单传输协议,它是一组用于由源…...
Android 适配手机和平板
一、屏幕适配限定符Android 系统加载应用资源时 , 会根据当前运行应用的设备的相关属性 , 如 : 屏幕尺寸 / 屏幕像素密度 / 宽高比 / 屏幕方向 等属性 , 加载不同的屏幕适配限定符目录下的资源 ;如 : 横竖屏切换时 , res/layout-land 目录中 , 存放的是横屏布局 , res/layout-p…...
时序预测 | MATLAB实现LSTM-SVR(长短期记忆神经网络-支持向量机)时间序列预测
时序预测 | MATLAB实现LSTM-SVR(长短期记忆神经网络-支持向量机)时间序列预测 目录时序预测 | MATLAB实现LSTM-SVR(长短期记忆神经网络-支持向量机)时间序列预测效果一览基本介绍模型介绍LSTM模型SVR模型LSTM-SVR模型程序设计参考资料致谢效果一览 基本介绍 本次运行测试环境MA…...
分阶段构建golang运行环境Dockerfile镜像
在开始这项工作之前大家可以先去看一下docker官方给出关于空镜像scratch的说明,采用官方简单的一句话就是:scratch是一个明确的空图像,特别是对于“从头开始”构建图像。分阶段构建镜像就会用到scratch这个空镜像,这样的好处是可以…...
Vue-cli脚手架在做些什么(源码角度分析)
什么是Vue脚手架?在学习初期,我们的项目往往需要借助webpack、vite等打包工具配置Vue的开发环境,但是在真实开发中我们不可能每个项目从头来完成所有的webpack配置,这样显得开发的效率会大大的降低;所有的真实开发中&a…...
【Nginx】|入门连续剧——安装
作者:狮子也疯狂 专栏:《Nginx从入门到超神》 坚持做好每一步,幸运之神自然会降临在你的身上 目录一. 🦁 前言Ⅰ. 🐇 为啥我们要使用Nginx?二. 🦁 搭建流程Ⅰ. 🐇 环境准备Ⅱ. &…...
从0开始学python -38
Python3 面向对象-1 Python从设计之初就已经是一门面向对象的语言,正因为如此,在Python中创建一个类和对象是很容易的。本章节我们将详细介绍Python的面向对象编程。 如果你以前没有接触过面向对象的编程语言,那你可能需要先了解一些面向对…...
算法设计与分析期末考试复习(二)
分治法 将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。最好使子问题的规模大致相同。 分解(Divide):将一个难以直接解决的大问题,分割成一些规模较小的子…...
九龙证券|4D毫米波雷达成市场新宠,相关概念股大涨,会贡献多少业绩?
近日,4D毫米波雷达成为A股新宠,相关概念股如经纬恒润(688326.SH)一周内涨幅接近20%,威孚高科(000581.SZ)5个买卖日内涨幅超越25%。 有音讯称特斯拉将在3月1日投资者活动日会宣告新款Model 3的全…...
Git天天用,不得不看的那些事
作为一个工作两年的开发同学,git是每天都要接触的工具。但IDEA对git的封装已经满足了日常的代码提交需求,所以一直是以点点点的形式进行代码提交与更新,几乎没用命令行提交过(现在想来也是有些惭愧),对于gi…...
IDE 文档注释使用,模板注释,ide配置templates
文档注释基于javadoc模板 类注释 /*** 暂无介绍** author admin* version 1.0.0* <dt><span class"simpleTagLabel">时间:</span></dt>* <dd>2023/2/24</dd>*/方法注释 /*** 暂无描述** author admin* param args */javadoc相…...
力扣-查询近30天活跃用户数
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:1141. 查询近30天活跃用户数二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.其他总结前言 一、题目&…...
企企通聚源池| 聚合海量资源全网寻源,赋能供采双方撮合交易
目前,我们正处于一个飞速发展的信息时代,随着大数据时代的来临,在企业的日常经营中,数据无处不在,各类数据的采集、整合、分析对企业的发展、决策有着十分重要的作用。数据管理作为企业一项重要的建设工作,…...
【算法数据结构体系篇class09】:链表问题:快慢指针、回文结构、复制、中点,分区、相交
一、链表解题的方法论 1)对于笔试,不用太在乎空间复杂度,一切为了时间复杂度2)对于面试,时间复杂度依然放在第一位,但是一定要找到空间最省的方法二、链表常用数据结构和技巧1)使用容器(哈希表、数组等)2)快…...
实验室信息化管理行业方案
为适应新时代下的管理机制与应用场景,越来越多的检测实验室需对研发部门和实验部门进行全面的、现代化的、电子化的综合管理,帮助检测机构对实验室的规划与计划、项目立项与管理、项目成果、合同,以及基建等工作进行统一的管理,而…...
docker学习
docker 环境搭建 MySql # mysql5.7 docker run --name mysql10 -p 3306:3306 -v D:\MySql\conf:/etc/mysql/conf.d -v D:\MySql\data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD123456 -d mysql:5.7docker run --name mysql10 -p 3306:3306 -v /etc/mysql/conf.d:/etc/mysql/co…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
