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

代码随想录算法训练营第三十九天【动态规划part02】 | 62.不同路径、63. 不同路径 II

62.不同路径

题目链接:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

求解思路:

动规五部曲

  1. 确定dp数组及其下标含义:dp[i][j] 表示从(0,0)出发,到(i,j)有dp[i][j] 条路径
  2. 确定递推公式:只能从左边或上边过来,因此 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  3. dp数组的初始化:第一行和第一列都初始化为1,因为从原点到[i][0]或[0][j]的路径只有一条
  4. 确定遍历顺序:因为当前值从上方和左方推导而来,因此从左到右,从上到下遍历
  5. 举例推导dp数组:如图所示

代码:

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n,0));// 将第一行和第一列初始化为1,因为只有一种路径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];}
};

63. 不同路径 II

题目链接:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

求解思路:

动规五部曲

  1. 确定dp数组及其下标含义:dp[i][j] 表示从(0,0)出发,到(i,j)有dp[i][j] 条路径
  2. 确定递推公式:只能从左边或上边过来, dp[i][j] = dp[i - 1][j] + dp[i][j - 1],注意如果有障碍物就跳过当前循环
  3. dp数组的初始化:第一行和第一列都初始化为1,因为从原点到[i][0]或[0][j]的路径只有一条;注意如果在第一行或第一列的某个位置有障碍物,则再往右或往下的道路就不通了,初始化应该停止
  4. 确定遍历顺序:因为当前值从上方和左方推导而来,因此从左到右,从上到下遍历
  5. 举例推导dp数组:如图所示,中间的位置是障碍物

代码:

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));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];}
};

相关文章:

代码随想录算法训练营第三十九天【动态规划part02】 | 62.不同路径、63. 不同路径 II

62.不同路径 题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 求解思路&#xff1a; 动规五部曲 确定dp数组及其下标含义&#xff1a;dp[i][j] 表示从&#xff08;0,0&#xff09;出发&#xff0c;到&#xff08;i,j&#x…...

鸿蒙4.0开发笔记之DevEco Studio如何使用Previewer窗口预览器(一)

一、预览器作用 DevEco Studio预览器概况在HarmonyOS应用开发过程中&#xff0c;通过使用预览器&#xff0c;可以查看应用的UI效果&#xff0c;方便开发者实时查看应用的运行效果&#xff0c;随时调整代码。 二、打开Previewer预览器 1、正常启动 打开预览器的位置在DevEco…...

音视频转换软件Permute mac中文板特点介绍

Permute mac是一款Mac平台上的媒体格式转换软件&#xff0c;由Chaotic Software开发。它可以帮助用户快速地将各种音频、视频和图像文件转换成所需格式&#xff0c;并提供了一些常用工具以便于用户进行编辑和处理。 Permute mac软件特点 - 支持大量格式&#xff1a;支持几乎所…...

前端uniapp列表下拉到底部加载下一页列表【下拉加载页面/带源码/实战】

目录 一. 图片1.2. 二.list.vue三.uni-load-more.vue最后 一. 图片 1. 2. 二.list.vue <template><view><!--列表--><scroll-view scroll-y"true" class"scroll-Y" :style"height: scrollviewHigh px;" lower-threshol…...

超聚变服务器关闭超线程CPU的步骤(完整版)

前言: 笨鸟先飞&#xff0c;好记性不如烂笔头。 我们项目都用不到超线程CPU&#xff0c;所以调测设备的时候都需要关掉&#xff0c;最近新设备换成了超聚变的服务器&#xff0c;这篇记录我关闭&#xff08;超聚变&#xff09;服务器超线程CPU的方法步骤。 关闭超线程CPU的步骤…...

智能驾驶汽车虚拟仿真视频数据理解(一)

赛题官网 datawhale 赛题介绍 跑通demo paddle 跑通demo torch 提交的障碍物取最主要的那个&#xff1f;不考虑多物体提交。障碍物&#xff0c;尽可能选择状态发生变化的物体。如果没有明显变化的&#xff0c;则考虑周边的物体。车的状态最后趋于减速、停止&#xff0c;时序…...

事关Django的静态资源目录设置(Django的setting.py中的三句静态资源(static)目录设置语句分别是什么作用?)

在Django的setting.py中常见的三句静态资源(static)目录设置语句如下&#xff1a; STATICFILES_DIRS [os.path.join(BASE_DIR, static)] STATIC_ROOT os.path.join(BASE_DIR, static) STATIC_URL /static/下面介绍这三句话的作用。 首先说第1句和第2句&#xff1a; STATI…...

Vue.js2+Cesium1.103.0 十四、绘制视锥,并可实时调整视锥姿态

Vue.js2Cesium1.103.0 十四、绘制视锥&#xff0c;并可实时调整视锥姿态 Demo <template><divid"cesium-container"style"width: 100%; height: 100%;"><divclass"control"style"position: absolute;right: 50px;top: 50px…...

批量替换WordPress文章内图片链接

在WordPress使用过程中&#xff0c;如果中途更换了域名&#xff0c;原先文章内的图片使用的是原来的域名&#xff0c;就会造成文章页里面的图片链接无法显示。如果从后台文章挨个修改就比较麻烦。可以通过数据库进行批量替换即可。 使用 PHPMyadmin 打开 数据库&#xff0c;登…...

关于DBMS_STATS.GATHER_DATABASE_STATS_JOB_PROC的一些发现

任务在哪 这个是11g以后的自动收集统计信息的后台任务&#xff0c;10g之前是在dba_scheduler_jobs里查看 SQL> SELECT CLIENT_NAME ,STATUS ,MEAN_INCOMING_TASKS_7_DAYS,MEAN_INCOMING_TASKS_30_DAYS FROM DBA_AUTOTASK_CLIENT WHERE…...

MatrixOne 支持多样化生态工具

近日&#xff0c;云原生数据库 MatrixOne 支持多样化生态工具&#xff0c;包括&#xff1a;数据集成工具、BI 工具和数据计算引擎这三类生态工具。 云原生数据库使得传统数据库得以充分结合云服务的免运维、高弹性、高可扩展、高可用、高性价比优势&#xff0c;又顺应了云端应…...

力扣刷题篇之位运算

系列文章目录 目录 系列文章目录 前言 一、位运算的基本运算 二、位运算的技巧 三、布隆过滤器 总结 前言 本系列是个人力扣刷题汇总&#xff0c;本文是数与位。刷题顺序按照[力扣刷题攻略] Re&#xff1a;从零开始的力扣刷题生活 - 力扣&#xff08;LeetCode&#xff0…...

asp.net core mvc 控制器使用配置

一、在根目录 添加 mysettings.json 文件 mysettings.json 文件代码如下&#xff1a; {"MySettings": {"Name": "独立配置文件","Site": "lt"} }appsettings.json 文件代码如下&#xff1a; {"Logging": {&quo…...

Hadoop学习总结(MapRdeuce的词频统计)

MapRdeuce编程示例——词频统计 一、MapRdeuce的词频统计的过程 二、编程过程 1、Mapper 组件 WordcountMapper.java package com.itcast.mrdemo;import org.apache.hadoop.io.IntWritable; import org.apache.hadoop.io.LongWritable; import org.apache.hadoop.io.Text; …...

PPT基础入门

目录 相关设置快捷键shift 快捷键Ctrl 快捷键Ctrl Shift 组合快捷键快捷键总结 相关设置 设置撤回次数 自动保存 图片压缩 字体嵌入&#xff1a;目的是在不同的电脑上保留已经设置好的字体 多格式导出 &#xff08;1&#xff09;可以导出PDF &#xff08;2&#xff09;可以导…...

Java 语言关键字有哪些

Java 语言关键字有哪些 分类关键字访问控制privateprotectedpublic类&#xff0c;方法和变量修饰符abstractclassextendsfinalimplementsinterfacenativenewstaticstrictfpsynchronizedtransientvolatileenum程序控制breakcontinuereturndowhileifelseforinstanceofswitchcase…...

Go vs Rust:文件上传性能比较

在本文中&#xff0c;主要测试并比较了Go—Gin和Rust—Actix之间的多部分文件上传性能。 设置 所有测试都在配备16G内存的 MacBook Pro M1 上执行。 软件版本为&#xff1a; Go v1.20.5Rust v1.70.0 测试工具是一个基于 libcurl 并使用标准线程的自定义工具&#xff0c;能…...

C# NAudio 音频库

C# NAudio 音频库 NAudio安装NAudio简述简单示例1录制麦克风录制系统声卡WAV格式播放MP3格式播放AudioFileReader读取播放音频MediaFoundationReader 读取播放音频 NAudio安装 项目>NuGet包管理器 搜索NAudio点击安装&#xff0c;自动安装依赖库。 安装成功后工具箱会新增…...

springcloudalibaba-3

一、Nacos Config入门 1. 搭建nacos环境【使用现有的nacos环境即可】 使用之前的即可 2. 在微服务中引入nacos的依赖 <!-- nacos配置依赖 --><dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-…...

异步复位同步释放与同步复位打拍

参考链接&#xff1a;复位系列之异步复位同步释放与同步复位打拍...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...