代码随想录第39天 | 62. 不同路径、63.不同路径II
62. 不同路径
动态规划五部曲:
- dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。
- 想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
- 首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。
- 从左到右一层一层遍历就可以了。这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
- 验证dp数组
/*** @param {number} m* @param {number} n* @return {number}*/
var uniquePaths = function (m, n) {let dp = new Array(m).fill().map(() => new Array(n))for (let i = 0; i < m; ++i) {dp[i][0] = 1}for (let i = 0; i < n; ++i) {dp[0][i] = 1}for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1]}}return dp[m - 1][n - 1]
};
63.不同路径II
比前一题多了障碍的限制条件。
五部曲:
- dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。
- 递推公式和62.不同路径一样,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。因为有了障碍,(i, j)如果就是障碍的话应该就保持初始状态(初始状态为0)。
- 如果(i, 0) 这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。
- 从左到右一层一层遍历,这样保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。
- 举例推导dp
/*** @param {number[][]} obstacleGrid* @return {number}*/
var uniquePathsWithObstacles = function (obstacleGrid) {let m = obstacleGrid.lengthlet n = obstacleGrid[0].lengthlet dp = new Array(m).fill().map(() => new Array(n).fill(0))for (let i = 0; i < m; i++) {if (obstacleGrid[i][0]) breakdp[i][0] = 1}for (let i = 0; i < n; i++) {if (obstacleGrid[0][i]) breakdp[0][i] = 1}for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]}}return dp[m - 1][n - 1]
};
相关文章:
代码随想录第39天 | 62. 不同路径、63.不同路径II
62. 不同路径 动态规划五部曲: dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。dp[i]…...
QMT入门—初识QMT
对于普通投资者来说,每天实时盯盘实在是无聊又无趣,特别是临时有事还会错过行情。如果能把自己的投资策略用代码实现,通过程序来自动买卖股票那该有多好,这样就不会错过行情也不会不按交易纪律来操作了。 解决办法有两种…...
C 语言的 return 语句
有返回值的函数要带 return 语句, return 后面是一个表达式, return 语句将表达式的值返回给主调函数. 一个函数也可以有多个 return 语句, 比如存在于不同的分支中, 但只能有一条 return 语句被执行, 然后程序的控制权就从被调函数传到主调函数. 对于有返回值但没有带 retur…...
企业级Vue路由角色权限应该怎么做?
角色权限 角色权限,简单来说就是登录的用户能看到系统的哪些页面,不能看到系统的哪些页面。一般是后台管理系统才会涉及到如此复杂的角色权限。 对于 vue 技术栈,实现角色权限一般有两种方式。 第一种是利用 beforeEach 全局前置守卫。 第…...
3.2.0 版本预告!Apache DolphinScheduler API 增强相关功能
Apache DolphinScheduler 3.2.0 版本即将发布,在此之前,为了让用户提前了解到大家所期待的新功能,我们制作了视频来”剧透“一些核心新发布。此前,我们比较全面地”剧透“的 3.2.0 版本的新功能,这次,我们来…...
测试工程师的工作
目录 1.何为软件测试工程师? 2.软件测试工程师的职责? 3.为什么要做软件测试? 4.软件测试的前途如何? 5.工具和思维谁更重要? 6.测试和开发相差大吗? 7.成为测试工程师的必备条件 8.测试的分类有哪…...
压力测试与测试工具jmeter的介绍
目录 一、性能指标 二、jmeter (一)JMeter 安装 (二)JMeter 压测示例 1、添加线程组 2、添加 HTTP 请求 3、添加监听器 4、启动压测&查看分析结果 (三)JMeter Address Already in use 错误解决 压力测…...
解析整型最大值(Integer.MIN_VALUE)溢出变为最小值(Integer.MAX_VALUE)
解析整型最大值(Integer.MIN_VALUE)溢出变为最小值(Integer.MAX_VALUE)结论分析 解析整型最大值(Integer.MIN_VALUE)溢出变为最小值(Integer.MAX_VALUE) 解析整型最大值(Integer.MIN_VALUE)溢出变为最小值(Integer.MAX_VALUE) ,java 二进制 最小值 减法 减1 结论 …...
【openpcdet】dbinfo内的信息
这就是kitti_dbinfos_train_sfd_seguv.pkl中【car】类别存储的信息。...
clickhouse查询缓存
为了实现最佳性能,数据库需要优化其内部数据存储和处理管道的每一步。但是数据库执行的最好的工作是根本没有完成的工作!缓存是一种特别流行的技术,它通过存储早期计算的结果或远程数据来避免不必要的工作,而访问这些数据的成本往…...
vue中使用Base64加密、解密以及des加密、解密
Base64加密、解密 第一步: npm install js-base64 --save 下载依赖 第二步: 直接引入即可 import { Base64 } from js-base64; 第三步: Base64.encode(xxxx) 其中 .encode() 加密 .decode() 解密 中间不需要使用加密的key等…...
关于丢失安卓秘钥的撞sha-1值的办法
实验得知,安卓sha-1和keytool生成秘钥签名文件的时间有关。 前提条件是,开发者必须知道生成秘钥的所有细节参数 以下是撞文件代码(重复生成) import time import osidx 0while True:cmdkeytool -keyalg RSA -genkeypair -alia…...
maven如何打包你会吗?
1.新建一个maven项目,在main/java中建立Main类 public class Main {public static void main(String[] args) {System.out.println("hello java ...");} } 2.添加依赖,使其成为可执行包 <build><plugins><!--打包成为可执行包-…...
idea 控制台 打印 Tomcat日志Tomcat Catalina Log控制台乱码问题
修改tomcat的日志配置文件 conf一>logging.properties 修改【1catalina.org.apache.juli.AsyncFileHandler.encoding】的值为gbk 1catalina.org.apache.juli.AsyncFileHandler.level FINE 1catalina.org.apache.juli.AsyncFileHandler.directory ${catalina.base}/logs 1…...
python我的世界
我的世界不知道大家有没有玩过,今天博主用python的Ursina库复刻了我的世界给大家分享 安装Ursina pip install ursina 导入Ursina from ursina import * from ursina.prefabs.first_person_controller import FirstPersonController 创建app app Ursina() 创建Voxe…...
SpringBoot+vue 大文件分片下载
学习链接 SpringBootvue文件上传&下载&预览&大文件分片上传&文件上传进度 Blob & File & FileReader & ArrayBuffer VueSpringBoot实现文件的分片下载 video标签学习 & xgplayer视频播放器分段播放mp4(Range请求交互过程可以参…...
scanf函数读取数据 清空缓冲区
scanf函数读取数据&清空缓冲区 scanf 从输入缓冲区读取数据数据的接收数据存入缓冲区scanf 中%d读取数据scanf中%c读取数据 清空输入缓冲区例子用getchar()吸收回车练习 scanf 从输入缓冲区读取数据 首先,要清楚的是,scanf在读取数据的时候ÿ…...
js 文件常用转换
获取上传文件的arrayBuffer:var u8arr await file.arrayBuffer() 通过arrayBuffer转换成Buffer:Buffer.from(u8arr) 1. Blob、File → Base64 function fileToDataURL(file) {let reader new FileReader();reader.readAsDataURL(file);reader.onload…...
基于Open3D的点云处理15-特征点
Intrinsic shape signatures (ISS) 参考 ISS关键点: 基本原理是避免在沿主要方向表现出类似分布的点上检测关键点,在这些点上无法建立可重复的规范参考框架,因此后续描述阶段很难变得有效。在剩余点中,显着性由最小特征值的大小决定,以便仅包…...
算法刷题Day 58 每日温度+下一个更大元素I
Day 58 单调栈 739. 每日温度 class Solution { public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> rst(temperatures.size());vector<int> decsStk; // 单调递减栈for (int i 0; i < temperatures.size(); i)…...
InfluxDB新手必看:从安装到基本操作的完整指南(Windows版)
InfluxDB Windows实战指南:从零搭建时序数据库系统 时序数据正成为物联网、DevOps和业务监控领域的核心资产。想象一下,您需要每秒处理数千台设备的温度读数,或者分析应用程序每分钟的性能指标——传统关系型数据库在这种高频写入场景下往往…...
避坑指南:用OpenCompass 0.2.4评测InternLM2时,为什么MMLU数据集必须用旧版?
避坑指南:OpenCompass 0.2.4评测InternLM2时MMLU数据集版本兼容性实战解析 当你在深夜调试大模型评测代码,屏幕突然弹出"Dataset version mismatch"的红色报错时,是否也经历过那种头皮发麻的崩溃感?最近我们团队在使用O…...
视频画面匹配软件 影视片段匹配软件出售 创作效率提升 速橙软件-相同视频片段匹配系统
免费下载链接:http://www.suchengai.cn/作为一名视频创作者或影视解说博主,你是否经常面临这样的困境?为了制作一个10分钟的视频解说,需要花费数小时甚至一整天的时间,在原始影片中手动查找和剪辑对应的片段。这不仅效…...
大数据领域 OLAP 技术的发展趋势展望
大数据领域OLAP技术的发展趋势展望 关键词:OLAP、大数据分析、实时决策、云原生、AI融合 摘要:本文从超市老板的"销售密码"故事出发,用通俗易懂的语言拆解OLAP(在线分析处理)技术的核心逻辑,结合当前大数据技术演进趋势,深入探讨OLAP在实时化、云原生化、AI融…...
服务器很卡,是CC攻击造成的吗
之前有客户反馈,服务器有一段时间使用总是会遇到卡的情况,查看并无流量攻击的情况,程序也未进行过什么修改,用户人数也没有什么变化。来咨询是什么原因导致的。导致机器卡的情况,一般有带宽不够,硬件性能不…...
解决Gradio share=True报错:手动下载并配置frpc_linux_amd64_v0.3文件的保姆级教程
解决Gradio shareTrue报错的完整实战指南:从手动配置frpc到深度优化 当你兴奋地准备向客户展示刚完成的Gradio应用时,却在终端看到红色的报错信息——shareTrue参数失效了。这种场景对开发者来说再熟悉不过:本地调试一切正常,但需…...
从零搭建到百万QPS:Python MCP服务器模板实战对比(含Docker镜像体积、CI/CD兼容性、调试友好度全维度打分)
第一章:从零搭建到百万QPS:Python MCP服务器模板实战对比总览在构建高并发、低延迟的MCP(Model Control Protocol)服务时,Python凭借其生态丰富性与开发效率成为主流选型之一,但原生GIL限制与异步模型差异常…...
Wan2.2-I2V-A14B私有部署镜像优势:零依赖冲突、开箱即用、免编译安装
Wan2.2-I2V-A14B私有部署镜像优势:零依赖冲突、开箱即用、免编译安装 1. 镜像核心价值与定位 Wan2.2-I2V-A14B私有部署镜像是专为文生视频场景打造的一站式解决方案。这个镜像最大的特点就是解决了AI模型部署中最让人头疼的环境配置问题,真正做到下载即…...
[Python3高阶编程] - 异步编程深度学习指南二: 同步原语
概述在 Python 异步编程中,虽然协程(coroutine)天然避免了线程切换开销,但多个协程仍可能同时访问共享资源(如全局变量、文件、数据库连接),从而引发竞态条件(Race Condition&#x…...
PyTorch 2.8镜像快速部署:5分钟验证torch.cuda.is_available()并启动API服务
PyTorch 2.8镜像快速部署:5分钟验证torch.cuda.is_available()并启动API服务 1. 镜像概述与环境准备 PyTorch 2.8深度学习镜像是一个开箱即用的高性能计算环境,专为现代AI工作负载优化。这个预配置环境能让你跳过繁琐的安装过程,直接进入模…...
