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

算法训练营 day43 动态规划 不同路径 不同路径 II

算法训练营 day43 动态规划 不同路径 不同路径 II

不同路径

62. 不同路径 - 力扣(LeetCode)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径

按照动规五部曲来分析:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。

  1. 确定递推公式

想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j]dp[i][j - 1]

此时在回顾一下 dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。

那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

  1. dp数组的初始化

如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

  1. 确定遍历顺序

这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] dp[i][j - 1]一定是有数值的。

  1. 举例推导dp数组
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];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];}
}

不同路径 II

63. 不同路径 II - 力扣(LeetCode)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

62.不同路径 中我们已经详细分析了没有障碍的情况,有障碍的话,其实就是标记对应的dp table(dp数组)保持初始值(0)就可以了。

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。

  1. 确定递推公式

递推公式和62.不同路径一样,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

但这里需要注意一点,因为有了障碍,(i, j)如果就是障碍的话应该就保持初始状态(初始状态为0)。

  1. dp数组如何初始化

因为从(0, 0)的位置到(i, 0)的路径只有一条,所以dp[i][0]一定为1,dp[0][j]也同理。

但如果(i, 0) 这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。

  1. 确定遍历顺序

从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出,一定是从左到右一层一层遍历,这样保证推导dp[i][j]的时候,dp[i - 1][j] dp[i][j - 1]一定是有数值。

  1. 举例推导dp数组
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][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];}
}

相关文章:

算法训练营 day43 动态规划 不同路径 不同路径 II

算法训练营 day43 动态规划 不同路径 不同路径 II 不同路径 62. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达…...

关联查询的SQL有几种情况

1、内连接&#xff1a;inner join … on 结果&#xff1a;A表 ∩ B表 2、左连接&#xff1a;A left join B on &#xff08;2&#xff09;A表全部 &#xff08;3&#xff09;A表- A∩B 3、右连接&#xff1a;A right join B on &#xff08;4&#xff09;B表全部 &#…...

查缺补漏三:事务隔离级别

什么是事务&#xff1f; 事务就是一组操作的集合&#xff0c;事务将整组操作作为一个整体&#xff0c;共同提交或者共同撤销 这些操作只能同时成功或者同时失败&#xff0c;成功即可提交事务&#xff0c;失败就执行事务回滚 MySQL的事务默认是自动提交的&#xff0c;一条语句执…...

没有她的通讯录(C语言实现)

&#x1f680;write in front&#x1f680; &#x1f4dd;个人主页&#xff1a;认真写博客的夏目浅石. &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd; &#x1f4e3;系列专栏&#xff1a;夏目的C语言宝藏 &#x1f4ac;总结&#xff1a;希望你看完之…...

Spring Security 从入门到精通

前言 Spring Security 是 Spring 家族中的一个安全管理框架。相比与另外一个安全框架Shiro&#xff0c;它提供了更丰富的功能&#xff0c;社区资源也比Shiro丰富。 一般来说中大型的项目都是使用SpringSecurity 来做安全框架。小项目有Shiro的比较多&#xff0c;因为相比与Spr…...

微信小程序Springboot vue停车场车位管理系统

系统分为用户和管理员两个角色 用户的主要功能有&#xff1a; 1.用户注册和登陆系统 2.用户查看系统的公告信息 3.用户查看车位信息&#xff0c;在线预约车位 4.用户交流论坛&#xff0c;发布交流信息&#xff0c;在线评论 5.用户查看地图信息&#xff0c;在线导航 6.用户查看个…...

看完这篇 教你玩转渗透测试靶机vulnhub——Hack Me Please: 1

Vulnhub靶机Hack Me Please: 1渗透测试详解Vulnhub靶机介绍&#xff1a;Vulnhub靶机下载&#xff1a;Vulnhub靶机安装&#xff1a;Vulnhub靶机漏洞详解&#xff1a;①&#xff1a;信息收集&#xff1a;②&#xff1a;漏洞利用③&#xff1a;获取反弹shell&#xff1a;④&#x…...

nodejs+vue地铁站自动售票系统-火车票售票系统vscode

地铁站自动售票系统主要包括个人中心、地铁线路管理、站点管理、购票信息管理、乘坐管理、用户信息管理等多个模块。它使用的是前端技术&#xff1a;nodejsvueelementui 前后端通讯一般都是采取标准的JSON格式来交互。前端技术&#xff1a;nodejsvueelementui,视图层其实质就是…...

Spring Security in Action 第十二章 OAuth 2是如何工作的?

本专栏将从基础开始&#xff0c;循序渐进&#xff0c;以实战为线索&#xff0c;逐步深入SpringSecurity相关知识相关知识&#xff0c;打造完整的SpringSecurity学习步骤&#xff0c;提升工程化编码能力和思维能力&#xff0c;写出高质量代码。希望大家都能够从中有所收获&#…...

天工开物 #5 我的 Linux 开发机

首先说一下结论&#xff1a;最终我选择了基于 Arch Linux[1] 的 Garuda Linux[2] 发行版作为基础来搭建自己的 Linux 开发机。Neofetch 时刻发行版的选择在上周末的这次折腾里&#xff0c;我一共尝试了 Garuda Linux 发行版&#xff0c;原教旨的 Arch Linux 发行版&#xff0c;…...

【沁恒WCH CH32V307V-R1开发板输出DAC实验】

【沁恒WCH CH32V307V-R1开发板输出DAC实验】1. 前言2. 软件配置2.1 安装MounRiver Studio3. DAC项目测试3.1 打开DAC工程3.2 编译项目4. 下载验证4.1 接线4.2 演示效果5. 小结1. 前言 数字/模拟转换模块&#xff08;DAC&#xff09;&#xff0c;包含 2 个可配置 8/12 位数字输入…...

Linux进程控制详解

目录前言一、进程创建1.1 fork函数初识1.2 写时拷贝1.3 fork常规用法1.4 fork调用失败的原因二、进程终止2.1 进程终止时&#xff0c;操作系统做了什么&#xff1f;&#xff1f;2.2 进程终止的常见方式有哪些&#xff1f;&#xff1f;2.3 如何用代码终止一个进程三、进程等待3.…...

C语言深度剖析之程序环境和预处理

1.程序的翻译环境和执行环境 第一种是翻译环境&#xff0c;在这个环境中源代码被转换为可执行的机器指令 第二种是执行环境&#xff0c;它用于实际执行代码 2.翻译环境 分为四个阶段 预编译阶段 &#xff0c;编译&#xff0c;汇编&#xff0c;链接 程序编译过程&#xff1a;多个…...

【Spark分布式内存计算框架——Spark Core】9. Spark 内核调度(上)

第八章 Spark 内核调度 Spark的核心是根据RDD来实现的&#xff0c;Spark Scheduler则为Spark核心实现的重要一环&#xff0c;其作用就是任务调度。Spark的任务调度就是如何组织任务去处理RDD中每个分区的数据&#xff0c;根据RDD的依赖关系构建DAG&#xff0c;基于DAG划分Stag…...

Vulkan教程(15): Graphics pipeline之Render passes(渲染通道)

Vulkan官方英文原文&#xff1a; https://vulkan-tutorial.com/Drawing_a_triangle/Graphics_pipeline_basics/Render_passes对应的Vulkan技术规格说明书版本&#xff1a; Vulkan 1.3.2Setup设置Before we can finish creating the pipeline, we need to tell Vulkan about the…...

乐观锁、雪花算法、MyBatis-Plus多数据源

乐观锁、雪花算法、MyBatis-Plus多数据源e>雪花算法2、乐观锁a>场景b>乐观锁与悲观锁c>模拟修改冲突d>乐观锁实现流程e>Mybatis-Plus实现乐观锁七、通用枚举a>数据库表添加字段sexb>创建通用枚举类型c>配置扫描通用枚举d>测试九、多数据源1、创建…...

详解Redisson分布式限流的实现原理

我们目前在工作中遇到一个性能问题&#xff0c;我们有个定时任务需要处理大量的数据&#xff0c;为了提升吞吐量&#xff0c;所以部署了很多台机器&#xff0c;但这个任务在运行前需要从别的服务那拉取大量的数据&#xff0c;随着数据量的增大&#xff0c;如果同时多台机器并发…...

[python入门㊹] - python测试类

目录 ❤ 断言方法 assertEqual 和 assertNotEqual assertTrue 和 assertFalse assertIsNone 和 assertIsNotNone ❤ 一个要测试的类 ❤ 测试AnonymousSurvey类 ❤ setUp() 和 teardown() 方法 ❤ 断言方法 常用的断言方法: 方法 用途 assertEqual(a, b) 核实a …...

Web 框架 Flask 快速入门(二)表单

课程地址&#xff1a;Python Web 框架 Flask 快速入门 文章目录&#x1f334; 表单1、表单介绍2、表单的简单实现1. 代码2. 代码的执行逻辑3、使用wtf扩展实现4、bug记录&#xff1a;表单验证总是失败&#x1f334; 表单 1、表单介绍 当我们在网页上填写账号密码进行登录的时…...

C++基础(5) - 复合类型(上)

文章目录数组1、什么是数组2、数组的声明3、数组的初始化4、数组的访问5、二维数组6、memset —— 给数组中每一个元素赋同样的值字符串&#xff08;字符数组&#xff09;1、string.h 头文件1.1 strlen()1.2 strcmp()1.3 strcpy()1.4 strcat()string 类简介1、C11 字符串初始化…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

Python异步编程:深入理解协程的原理与实践指南

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 持续学习&#xff0c;不断…...

2025年全国I卷数学压轴题解答

第19题第3问: b b b 使得存在 t t t, 对于任意的 x x x, 5 cos ⁡ x − cos ⁡ ( 5 x t ) < b 5\cos x-\cos(5xt)<b 5cosx−cos(5xt)<b, 求 b b b 的最小值. 解: b b b 的最小值 b m i n min ⁡ t max ⁡ x g ( x , t ) b_{min}\min_{t} \max_{x} g(x,t) bmi…...

设计模式域——软件设计模式全集

摘要 软件设计模式是软件工程领域中经过验证的、可复用的解决方案&#xff0c;旨在解决常见的软件设计问题。它们是软件开发经验的总结&#xff0c;能够帮助开发人员在设计阶段快速找到合适的解决方案&#xff0c;提高代码的可维护性、可扩展性和可复用性。设计模式主要分为三…...