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

代码随想录训练营第三十四天| 62.不同路径 63. 不同路径 II

 62.不同路径   

题目链接:62. 不同路径 - 力扣(LeetCode)

讲解链接:代码随想录

动态规划五步走

1 定义dp数组是到dp[i][j]时有dp[i][j]条路径

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

2 找递推公式 

从题目中知道 dp[i][j]只能从上方或者左方来 所以当前路径数 = 上方路径数 + 左方路径数

就是这一行 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

3 初始化dp 因为只能向下或者向左走 那其实在0行i列和0行j列都只能从起点开始并且到达当前位置的路径只能是1 所以 dp[0][j] =1; dp[i][0] =1;

4 确定遍历顺序 那就直接从前往后 有固定值 也不会有空值

5 推导一下 发现结果如图(代码随想录):

Java代码:

class Solution{public static 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 i = 0; i < n; i++){dp[0][i] = 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];}
}

 63. 不同路径 II   

题目链接:

讲解链接:

 和上题思路一致 但是需要考虑障碍物位置 

障碍物在 起点 在 终点 在 遍历过程中的情况 grid[i][j] = 1代表当前位置有障碍物 

一旦有 则 在初始化dp[0][j] 和 dp[i][0](第一行和第一列的值)需要停下 而且在其障碍物以后的路径数为0

在递推公式里加了判断当前位置是否为障碍物

 dp[i][j] = (grid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;

Java代码:

class Solution{public int uniquePathsWithObstacles(int[][] grid){int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];//如果在起点或终点出现障碍 直接返回0if(grid[m - 1][n - 1] == 1 || grid[0][0] == 1){return 0;}for(int i = 0; i < m && grid[i][0] == 0; i++){dp[i][0] = 1;}for(int j = 0; j < n && grid[0][j] == 0; j++){dp[0][j] = 1;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[i][j] = (grid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
}

 打卡打卡

相关文章:

代码随想录训练营第三十四天| 62.不同路径 63. 不同路径 II

62.不同路径 题目链接&#xff1a;62. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 讲解链接&#xff1a;代码随想录 动态规划五步走 1 定义dp数组是到dp[i][j]时有dp[i][j]条路径 dp[i][j] &#xff1a;表示从&#xff08;0 &#xff0c;0&#xff09;出发&#xf…...

V90伺服PN版组态配置<一>

1、添加PLC之后&#xff0c;继续博图中网络视图中添加新设备&#xff0c;添加伺服驱动器组态设备 2、SINAMICS V90 PN V1.0 3、修改驱动器的IP地址。 【注意】 在项目中提前做好项目规划&#xff0c;如PLC设备从192.168.0.1开始&#xff0c;顺序递增------个位数都是CPU设备…...

又一年。。。。。。

2024&#xff0c;浑浑噩噩的一年。 除了100以内的加减法&#xff08;数据&#xff0c;数据&#xff0c;还是数据。。。。。。&#xff09;&#xff0c;似乎没做些什么。 脸盲症越来越重的&#xff0c;怕是哪天连自己都不认得自己的了。 看到什么&#xff0c;听到什…...

xterm + vue3 + websocket 终端界面

xterm.js 下载插件 // xterm npm install --save xterm// xterm-addon-fit 使终端适应包含元素 npm install --save xterm-addon-fit// xterm-addon-attach 通过websocket附加到运行中的服务器进程 npm install --save xterm-addon-attach <template><div :…...

医疗数仓业务数据采集与同步

业务数据采集与同步 业务采集组件配置业务数据同步概述数据同步策略选择数据同步工具概述1.1.4 全量表数据同步DataX配置文件生成全量表数据同步脚本增量表数据同步 MySQL - Maxwell - Kafka - Flume - HDFSMaxwell配置增量表首日全量同步 业务采集组件配置 Maxwell将业务采集到…...

数字孪生智慧水利与水务所包含的应用场景有哪些?二者有何区别

水利和水务是两个密切相关但有所区别的概念&#xff0c;它们在水资源管理和保护方面各自承担着不同的职责和功能。 定义 智慧水务&#xff1a;智慧水务是指通过物联网、大数据、云计算、人工智能等新一代信息技术&#xff0c;对城市供水、排水、污水处理、水质监测等水务系统…...

Qt Creator项目构建配置说明

QT安装好之后&#xff0c;在安装目录的Tools\QtCreator\bin下找到qtcreator.exe文件并双击打开 点击文件-新建文件或项目 选择Qt Widgets Application 设置项目名称以及路径 make工具选择qmake&#xff08;cmake还未尝试过&#xff09; 设置主界面对应类的名称、父类&#…...

进程间通信的“五大武器”

&#x1f604;作者简介&#xff1a; 小曾同学.com,一个致力于测试开发的博主⛽️&#xff0c;主要职责&#xff1a;测试开发、CI/CD 如果文章知识点有错误的地方&#xff0c;还请大家指正&#xff0c;让我们一起学习&#xff0c;一起进步。 &#x1f60a; 座右铭&#xff1a;不…...

全国青少年信息学奥林匹克竞赛(信奥赛)备考实战之循环结构(for循环语句)(六)

实战训练1—输出九九乘法表 问题描述: 在学校里学过九九乘法表&#xff0c;编程实现打印九九乘法表。 输入格式&#xff1a; 无输入 输出格式&#xff1a; 1*11 2*12 2*24 3*13 3*26 3*39 4*14 4*28 4*312 4*416 5*15 5*210 5*315 5*420 5*525 6*16 6*212 6*318 6*424 6*5…...

封装echarts成vue component

封装echarts成vue component EChartsLineComponent 文章目录 封装echarts成vue component EChartsLineComponent封装说明重写重点EChartsLineComponent的源码 使用说明调用EChartsLineComponent示例源码 封装说明 为了减少一些公共代码和方便使用echarts的line图形&#xff0c…...

uniapp Stripe 支付

引入 Stripe npm install stripe/stripe-js import { loadStripe } from stripe/stripe-js; Stripe 提供两种不同类型组件 Payment Element 和 Card Element&#xff1a;如果你使用的是 Payment Element&#xff0c;它是一个更高级别的组件&#xff0c;能够自动处理多种支…...

Windows onnxruntime编译openvino

理论上来说&#xff0c;可以直接访问 ONNXRuntime Releases 下载 dll 文件&#xff0c;然后从官方文档中下载缺少的头文件以直接调用&#xff0c;但我没有尝试过。 1. 下载 OpenVINO 包 从官网下载 OpenVINO 的安装包并放置在 C:\Program Files (x86) 路径下&#xff0c;例如…...

vue3+TS+vite中Echarts的安装与使用

概述 技术栈&#xff1a;Vue3TsViteEcharts 简述&#xff1a;图文详解&#xff0c;教你如何在Vue项目中引入Echarts&#xff0c;封装Echarts组件&#xff0c;并实现常用Echats图列 文章目录 一&#xff0c;效果图 二&#xff0c;引入Echarts 2.1安装Echarts 2.2main.ts中引…...

期末算法分析程序填空题

目录 5-1 最小生成树&#xff08;普里姆算法&#xff09; 5-2 快速排序&#xff08;分治法&#xff09; 输入样例&#xff1a; 输出样例&#xff1a; 5-3 归并排序(递归法) 输入样例&#xff1a; 输出样例&#xff1a; 5-4 求解编辑距离问题&#xff08;动态规划法&#xff09;…...

搭建android开发环境 android studio

1、环境介绍 在进行安卓开发时&#xff0c;需要掌握java&#xff0c;需要安卓SDK&#xff0c;需要一款编辑器&#xff0c;还需要软件的测试环境&#xff08;真机或虚拟机&#xff09;。 早起开发安卓app&#xff0c;使用的是eclipse加安卓SDK&#xff0c;需要自行搭建。 目前开…...

R语言6种将字符转成数字的方法,写在新年来临之际

咱们临床研究中&#xff0c;拿到数据后首先要对数据进行清洗&#xff0c;把数据变成咱们想要的格式&#xff0c;才能进行下一步分析&#xff0c;其中数据中的字符转成数字是个重要的内容&#xff0c;因为字符中常含有特殊符号&#xff0c;不利于分析&#xff0c;转成数字后才能…...

RocketMQ学习笔记(持续更新中......)

目录 1. 单机搭建 2. 测试RocketMQ 3. 集群搭建 4. 集群启动 5. RocketMQ-DashBoard搭建 6. 不同类型消息发送 1.同步消息 2. 异步消息发送 3. 单向发送消息 7. 消费消息 1. 单机搭建 1. 先从rocketmq官网下载二进制包&#xff0c;ftp上传至linux服务器&#xff0c…...

强化学习的基础概念

这节课会介绍一些基本的概念&#xff0c;并结合例子讲解。 在马尔科夫决策框架下介绍这些概念 本博客是基于西湖大学强化学习课程的视屏进行笔记的&#xff0c;这是链接&#xff1a; 课程链接 目录 强化学习的基本概念 state和state space Action和Action Space State transiti…...

excel怎么删除右边无限列(亲测有效)

excel怎么删除右边无限列&#xff08;亲测有效&#xff09; 网上很多只用第1步的&#xff0c;删除了根本没用&#xff0c;还是存在&#xff0c;但是隐藏后取消隐藏却是可以的。 找到右边要删除的列的第一个空白列&#xff0c;选中整个列按“ctrlshift>(向右的小箭头)”&am…...

STM32-笔记23-超声波传感器HC-SR04

一、简介 HC-SR04 工作参数&#xff1a; • 探测距离&#xff1a;2~600cm • 探测精度&#xff1a;0.1cm1% • 感应角度&#xff1a;<15 • 输出方式&#xff1a;GPIO • 工作电压&#xff1a;DC 3~5.5V • 工作电流&#xff1a;5.3mA • 工作温度&#xff1a;-40~85℃ 怎么…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

今日科技热点速览

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

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...