当前位置: 首页 > news >正文

【代码随想录训练营】【Day39】第九章|动态规划|62.不同路径|63. 不同路径 II

不同路径

题目详细:LeetCode.62

有点简单呀,做类似这种题型时,最好就是先画图:

  • 可以像题目一样,画一个二维表格,表格内的值代表到达这个格子的不同路径总数
  • 那么已知,如果图的大小为m == 1 || n == 1时,即只有一列或一行时,那么其不同路径总数都只有一条
  • 当出现其他情况时,我们并不难发现格子内的数值刚好等于其上边和左边格子的和,即其不同路径总数为经过上边和左边格子的不同路径之和
  • 那么我们以此规律就可以依次计算出除第一列和第一行外,到达其他各个格子的不同路径数目
  • 最后我们即可得到右下角终点的值,即为到达终点的不同路径总数

详细的解题思路我都写在注释里了,也可查阅:《代码随想录》— 不同路径

Java解法(动态规划):

class Solution {public int uniquePaths(int m, int n) {// 只有一列或一行时,那么其不同路径总数都只有一条if(m == 1 || n == 1){return 1;}// 主要初始化第一行和第一列的不同路径数都为1int[][] map = new int[m][n];for(int i = 0; i < m; i++){Arrays.fill(map[i], 1);}// 动态规划:从左往右,从上往下,计算到达每一个格子的不同路径总数for(int i = 1, j = 1; i < m;){// 递推公式map[i][j] = map[i - 1][j] + map[i][j - 1];// 先从左往右j++;if(j == n){// 到达右边界后,初始化列的下标j = 1;// 从上往下i++;}}return map[m - 1][n - 1];}
}

不同路径 II

题目详细:LeetCode.63

与上一题的区别在于这道题增加了障碍物,不过思路也不难,只要注意以下几点:

  • 如果起点或终点出现了障碍物,则最终的不同路径总数都为0
  • 对于第一列和第一行的初始化,按照从左往右,从上往下的顺序依次初始化为1,如果路径中出现了障碍物,则说明此路不通,后续的格子都初始化为0
  • 将有障碍物的格子的不同路径总数记作0,只有遇到无障碍物的格子才累计其不同路径数目

那么只要根据以上三点,进行相对应的逻辑处理即可,累计格子的不同路径数目的思路与上一题的思路无异,详细的解题思路我都写在注释里了,也可查阅:《代码随想录》— 不同路径 II

Java解法(动态规划):

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length, n = obstacleGrid[0].length;// 特判,当障碍物出现在终点或起点时,不同路径总数都为0if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1){return 0;}// 定义一个辅助二维数组dp,防止直接操作原数组时,出现obstacleGrid[i][j] == 1的情况,将障碍物的表示数值累加进路径总数中int[][] dp = new int[m][n];// 对第一列和第一行进行赋值,路径总数为1,但是当路线上出现障碍物时,其后续的格子的路径总数都为0for(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;}// 从左往右,从上往下记录到达每个格子的不同路径数目// 这里利用二维数组dp来记录到达各个格子的路径总数// 而obstacleGrid相当于地图,仅用于判断是否出现障碍物for(int i = 1, j = 1; i < m;){if(i >= m || j >= n) break;// 格子没障碍物才进行累计,有障碍物的格子其路径总数默认为0if(obstacleGrid[i][j] == 0)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];if(n == ++j){j = 1;i++;}}return dp[m - 1][n - 1];}
}

相关文章:

【代码随想录训练营】【Day39】第九章|动态规划|62.不同路径|63. 不同路径 II

不同路径 题目详细&#xff1a;LeetCode.62 有点简单呀&#xff0c;做类似这种题型时&#xff0c;最好就是先画图&#xff1a; 可以像题目一样&#xff0c;画一个二维表格&#xff0c;表格内的值代表到达这个格子的不同路径总数那么已知&#xff0c;如果图的大小为m 1 || n…...

【Linux】linux | 修改系统编码 |  增加字体处理 | 图片处理字体变成方块

一、说明1、CentOS7二、修改系统编码编辑文件vi /etc/locale.conf修改编码并保存LANGzh_CN.UTF-8配置生效source /etc/locale.conf1&#xff09;修改系统编码&#xff0c;只是让系统支持中文编码2&#xff09;不解决文字不显示的问题&#xff1b;往后看三、解决字体不显示问题非…...

R语言介绍及安装教程

R语言是一种免费的开源编程语言和环境&#xff0c;主要用于数据分析、统计建模和可视化。它可以运行在不同的操作系统上&#xff0c;如Windows、MacOS和Linux。R语言具有以下特点&#xff1a;丰富的数据处理和统计分析函数库&#xff1b;易于学习和使用&#xff1b;可以生成高质…...

Linux 练习九 (IPC 消息队列)

文章目录消息队列有亲缘关系的进程使用消息队列通信无亲缘关系的进程使用消息队列通信使用环境&#xff1a;Ubuntu18.04 使用工具&#xff1a;VMWare workstations &#xff0c;xshell作者在学习Linux的过程中对常用的命令进行记录&#xff0c;通过思维导图的方式梳理知识点&am…...

在Win 11下使用Visual Studio 2019和cygwin编译JBR(Java SDK 17)源码

很多文章介绍了JDK 8和JDK11源码在Linux编译&#xff0c;很少有人介绍了JDK 17在windows的编译过程&#xff0c;所以写了这篇文章&#xff0c;为什么选用JBR 17版本&#xff0c;因为JBR17 版本集成了HotSwapAgent功能&#xff0c;具体HotSwapAgent有什么用&#xff0c;请看我前…...

java基础学习 day51 (匿名内部类)

1. 什么是匿名内部类&#xff1f; 隐藏了名字的内部类&#xff0c;实际名字为&#xff1a;外部类名$序号可以写在成员位置&#xff0c;为没有名字的成员内部类也可以写在局部位置&#xff0c;为没有名字的局部内部类 2. 匿名内部类的格式&#xff1f; new 类名/接口名() { 重…...

Spring MVC程序开发(三大功能)

文章目录一、什么是Spring MVC?1.MVC定义2.MVC与Spring MVC的关系3.创建方式二、Spring MVC的核心功能1.连接功能浏览器获取前端接口和后端程序连接功能实现get和post的区别Spring Boot热部署2.获取参数&#xff08;1&#xff09;传递单个参数&#xff08;2&#xff09;传递对…...

stack,queue

stack,queuestack的介绍和使用介绍使用模拟实现queue的介绍和使用介绍使用模拟实现priority_queue的介绍和使用介绍使用模拟实现容器适配器概念标准库中stack&#xff0c;queue的底层结构介绍deque原理缺陷deque作为stack,queue底层默认容器stack的介绍和使用 介绍 stack是适…...

shiro反序列化

shiro550反序列化 | 清风的博客这个看着更舒服点 环境搭建 JDK&#xff1a;1.7 Tomcat&#xff1a;8.5.83 shiro源码&#xff1a;下载地址&#xff1a;https://codeload.github.com/apache/shiro/zip/shiro-root-1.2.4 shiro war包&#xff1a;下载地址SHIRO-550/samples-…...

【GoF 23 概念理解】IoC/DI(控制反转/依赖注入)

搞清楚以下几个问题你就明白什么是 IoC/DI 了&#xff1a; 参与者都有谁&#xff1f;依赖&#xff1a;谁依赖于谁&#xff1f;为什么要依赖&#xff1f;注入&#xff1a;谁注入于谁&#xff1f;到底注入什么&#xff1f;控制反转&#xff1a;谁控制谁&#xff1f;控制什么&…...

stm32外设-GPIO

0. 写在最前 本栏目笔记都是基于stm32F10x 1. GPIO基本介绍 GPIO—general purpose intput output 是通用输入输出端口的简称&#xff0c;简单来说就是软件可控制的引脚&#xff0c; STM32芯片的GPIO引脚与外部设备连接起来&#xff0c;从而实现与外部通讯、控制以及数据采集的…...

AfxMessageBox 自定义封装

一般情况下AfxMessageBox是系统提供的一个对话框&#xff0c;若要做这种效果的&#xff0c;必须重写。 实例1&#xff1a; void test_SgxMemDialog_AutoSize() { //使用给定大小的对话框 CSgxMemDialog dlg(180, 60); dlg.SetWindowTitle(_T(" SegeX - CT&qu…...

登入vCenter显示503,证书过期解决办法

登入vCenter显示503 原因&#xff1a;当安全令牌服务 &#xff08;STS&#xff09; 证书已过期时&#xff0c;会出现这些问题。这会导致内部服务和解决方案用户无法获取有效令牌&#xff0c;从而导致无法按预期运行&#xff08;证书两年后就会过期&#xff09;。 解决办法&…...

设计模式(十九)----行为型模式之命令模式

1、概述 日常生活中&#xff0c;我们出去吃饭都会遇到下面的场景。 定义&#xff1a; 将一个请求封装为一个对象&#xff0c;使发出请求的责任和执行请求的责任分割开。这样两者之间通过命令对象进行沟通&#xff0c;这样方便将命令对象进行存储、传递、调用、增加与管理。命…...

【数据库】数据库基础架构

数据库架构 数据库对于后端程序员来说是每天都需要打交道的系统&#xff0c;因此了解并掌握MySQL底层原理是必须的。 基础架构图 MySQL内部分为两层&#xff0c;一个是Server层&#xff0c;另一个是存储引擎层&#xff0c;而我们常用的就是MyISAM、InnoDB&#xff0c;主要负…...

English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三

English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三&#x1f48c;发音小贴士&#xff1a;&#x1f48c;当日目标音发音规则/技巧:&#x1f36d; Part 1【热身练习】&#x1f36d; Part2【练习内容】&#x1f36d;【练习感受】&#x1f353;元音 [ɔ…...

C++语法规则4(C++面向对象)

接口&#xff08;抽象类&#xff09; 接口描述了类的行为和功能&#xff0c;而不需要完成类的特定实现。C 接口是使用抽象类来实现的&#xff0c;抽象类与数据抽象互不混淆&#xff0c;数据抽象是一个把实现细节与相关的数据分离开的概念。 如果类中至少有一个函数被声明为纯虚…...

【Spring 深入学习】AOP的前世今生之后续

AOP的前世今生之后续 1. 概述 上篇文章【Spring 深入学习】AOP的前世今生之代理模式我们讲述了代理模式。而我们今天的主人公AOP就是基于代理模式实现的&#xff0c;所以我们今天会简单学习下AOP 2. 什么是AOP 是面向切面编程&#xff0c;一般可以帮助我们在不修改现有代码的情…...

软考高项——配置管理

配置管理配置管理配置管理6个主要活动配置项配置基线配置项的状态配置库配置库权限管理配置审计配置管理 配置管理的总线索包括&#xff1a; 1&#xff09;配置管理6个主要活动 2&#xff09;配置项 3&#xff09;配置基线 4&#xff09;配置项的状态 5&#xff09;配置库 6&a…...

网站SEO优化,网站TDK三大标签SEO优化,LOGO SEO优化

SEO&#xff08;Search Engine Optimization&#xff09;汉译为搜索引擎优化&#xff0c;是一种利用搜索引擎的规则提高网站在有关搜索 引擎内自然排名的方式。 SEO 的目的是对网站进行深度的优化&#xff0c;从而帮助网站获取免费的流量&#xff0c;进而在搜索引擎上提升网站的…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...