当前位置: 首页 > 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;复位系列之异步复位同步释放与同步复位打拍...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...