当前位置: 首页 > 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;进而在搜索引擎上提升网站的…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...