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

AI应用安全实战:基于Rebuff框架构建提示词注入防御体系

1. 项目概述&#xff1a;一个为AI应用量身定制的“输入防火墙”最近在折腾AI应用安全&#xff0c;特别是针对提示词注入&#xff08;Prompt Injection&#xff09;的防御&#xff0c;发现了一个非常对味的开源工具——protectai/rebuff。简单来说&#xff0c;Rebuff是一个专门设…...

家政派单小程序源头厂家

随着现代生活节奏的加快&#xff0c;家政服务的需求日益增长。为了满足这一需求&#xff0c;许多公司开始推出家政派单小程序&#xff0c;以提供更便捷、高效的服务体验。然而&#xff0c;在众多的选择面前&#xff0c;如何找到一家真正能够满足自身业务需求的源头厂家呢&#…...

ADAS环视系统与视频解码器关键技术解析

1. ADAS环视系统技术解析1.1 汽车安全技术演进路径从ABS防抱死系统到安全气囊&#xff0c;再到如今的ADAS&#xff08;高级驾驶辅助系统&#xff09;&#xff0c;汽车安全技术在过去二十年经历了三次重大迭代。德国车企在这个领域始终保持着技术领先&#xff0c;最早实现了车道…...

TradingView-ML-GUI:量化交易者的机器学习策略可视化实验平台

1. 项目概述&#xff1a;一个为交易者打造的机器学习图形界面 如果你是一个对量化交易和机器学习都感兴趣的开发者或交易员&#xff0c;大概率遇到过这样的困境&#xff1a;你有一个绝佳的交易策略想法&#xff0c;也懂一些机器学习模型&#xff0c;但每次想验证一个想法&…...

告别DCOM配置烦恼:用Python2.7 + OpenOPC的Open模式轻松搞定跨平台OPC-DA数据采集

工业数据采集新范式&#xff1a;Python2.7OpenOPC Gateway的轻量化实践 在工业自动化领域&#xff0c;数据采集系统如同神经末梢&#xff0c;将现场设备的实时状态转化为可分析的数字信号。传统OPC-DA方案依赖Windows平台的DCOM组件&#xff0c;配置复杂度与跨平台限制成为工程…...

8.4.3 开始屏幕和任务栏的优化:StartAllBack 找回高效 Windows 11 使用体验

&#x1f525; 个人主页&#xff1a; 杨利杰YJlio ❄️ 个人专栏&#xff1a; 《Sysinternals实战教程》 《Windows PowerShell 实战》 《WINDOWS教程》 《IOS教程》 《微信助手》 《锤子助手》 《Python》 《Kali Linux》 《那些年未解决的Windows疑难杂症》 &#x1f31f; 让…...

3406硬核量化总结:黄大年茶思屋34期5题全解 重塑华为全球全栈技术霸权战略

华夏之光永存・硬核总结:黄大年茶思屋5题全解对华为战略的决定性价值 一、华为核心战略:全栈自主可控,构建端边云网芯一体化技术霸权 华为的核心战略是根技术全自研、全链路闭环、全场景覆盖,以芯片为底座、网络为联接、操作系统为中枢、AI为引擎、云为载体、行业应用为出…...

ThreeFingerDragOnWindows:在Windows上实现macOS三指拖动的终极指南

ThreeFingerDragOnWindows&#xff1a;在Windows上实现macOS三指拖动的终极指南 【免费下载链接】ThreeFingersDragOnWindows Enables macOS-style three-finger dragging functionality on Windows Precision touchpads. 项目地址: https://gitcode.com/gh_mirrors/th/Three…...

深入AMD Ryzen硬件调试:SMUDebugTool技术原理与高级应用指南

深入AMD Ryzen硬件调试&#xff1a;SMUDebugTool技术原理与高级应用指南 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: http…...

Agent 应用时代将至,传统基础设施面临挑战,openYuanrong 等系统或成破局关键

Agent 应用时代已至自本轮大模型技术爆发以来&#xff0c;Agent 得到了广泛关注。进入 2026 年后&#xff0c;伴随 OpenClaw 的现象级爆火&#xff0c;Agent 更是彻底破圈&#xff0c;进入了更广阔的大众视野。同时&#xff0c;如果说以往的 Agent 更多用于 Demo 或一些相对定制…...