代码随想录算法训练营第三十九天 | 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…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
