代码随想录算法训练营第三十九天【动态规划part02】 | 62.不同路径、63. 不同路径 II
62.不同路径
题目链接:
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
求解思路:
动规五部曲
- 确定dp数组及其下标含义:dp[i][j] 表示从(0,0)出发,到(i,j)有dp[i][j] 条路径
- 确定递推公式:只能从左边或上边过来,因此 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- dp数组的初始化:第一行和第一列都初始化为1,因为从原点到[i][0]或[0][j]的路径只有一条
- 确定遍历顺序:因为当前值从上方和左方推导而来,因此从左到右,从上到下遍历
- 举例推导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)官网 - 全球极客挚爱的技术成长平台
求解思路:
动规五部曲
- 确定dp数组及其下标含义:dp[i][j] 表示从(0,0)出发,到(i,j)有dp[i][j] 条路径
- 确定递推公式:只能从左边或上边过来, dp[i][j] = dp[i - 1][j] + dp[i][j - 1],注意如果有障碍物就跳过当前循环
- dp数组的初始化:第一行和第一列都初始化为1,因为从原点到[i][0]或[0][j]的路径只有一条;注意如果在第一行或第一列的某个位置有障碍物,则再往右或往下的道路就不通了,初始化应该停止
- 确定遍历顺序:因为当前值从上方和左方推导而来,因此从左到右,从上到下遍历
- 举例推导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.不同路径 题目链接: 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 求解思路: 动规五部曲 确定dp数组及其下标含义:dp[i][j] 表示从(0,0)出发,到(i,j&#x…...
鸿蒙4.0开发笔记之DevEco Studio如何使用Previewer窗口预览器(一)
一、预览器作用 DevEco Studio预览器概况在HarmonyOS应用开发过程中,通过使用预览器,可以查看应用的UI效果,方便开发者实时查看应用的运行效果,随时调整代码。 二、打开Previewer预览器 1、正常启动 打开预览器的位置在DevEco…...
音视频转换软件Permute mac中文板特点介绍
Permute mac是一款Mac平台上的媒体格式转换软件,由Chaotic Software开发。它可以帮助用户快速地将各种音频、视频和图像文件转换成所需格式,并提供了一些常用工具以便于用户进行编辑和处理。 Permute mac软件特点 - 支持大量格式:支持几乎所…...
前端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的步骤(完整版)
前言: 笨鸟先飞,好记性不如烂笔头。 我们项目都用不到超线程CPU,所以调测设备的时候都需要关掉,最近新设备换成了超聚变的服务器,这篇记录我关闭(超聚变)服务器超线程CPU的方法步骤。 关闭超线程CPU的步骤…...
智能驾驶汽车虚拟仿真视频数据理解(一)
赛题官网 datawhale 赛题介绍 跑通demo paddle 跑通demo torch 提交的障碍物取最主要的那个?不考虑多物体提交。障碍物,尽可能选择状态发生变化的物体。如果没有明显变化的,则考虑周边的物体。车的状态最后趋于减速、停止,时序…...
事关Django的静态资源目录设置(Django的setting.py中的三句静态资源(static)目录设置语句分别是什么作用?)
在Django的setting.py中常见的三句静态资源(static)目录设置语句如下: STATICFILES_DIRS [os.path.join(BASE_DIR, static)] STATIC_ROOT os.path.join(BASE_DIR, static) STATIC_URL /static/下面介绍这三句话的作用。 首先说第1句和第2句: STATI…...
Vue.js2+Cesium1.103.0 十四、绘制视锥,并可实时调整视锥姿态
Vue.js2Cesium1.103.0 十四、绘制视锥,并可实时调整视锥姿态 Demo <template><divid"cesium-container"style"width: 100%; height: 100%;"><divclass"control"style"position: absolute;right: 50px;top: 50px…...
批量替换WordPress文章内图片链接
在WordPress使用过程中,如果中途更换了域名,原先文章内的图片使用的是原来的域名,就会造成文章页里面的图片链接无法显示。如果从后台文章挨个修改就比较麻烦。可以通过数据库进行批量替换即可。 使用 PHPMyadmin 打开 数据库,登…...
关于DBMS_STATS.GATHER_DATABASE_STATS_JOB_PROC的一些发现
任务在哪 这个是11g以后的自动收集统计信息的后台任务,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 支持多样化生态工具
近日,云原生数据库 MatrixOne 支持多样化生态工具,包括:数据集成工具、BI 工具和数据计算引擎这三类生态工具。 云原生数据库使得传统数据库得以充分结合云服务的免运维、高弹性、高可扩展、高可用、高性价比优势,又顺应了云端应…...
力扣刷题篇之位运算
系列文章目录 目录 系列文章目录 前言 一、位运算的基本运算 二、位运算的技巧 三、布隆过滤器 总结 前言 本系列是个人力扣刷题汇总,本文是数与位。刷题顺序按照[力扣刷题攻略] Re:从零开始的力扣刷题生活 - 力扣(LeetCode࿰…...
asp.net core mvc 控制器使用配置
一、在根目录 添加 mysettings.json 文件 mysettings.json 文件代码如下: {"MySettings": {"Name": "独立配置文件","Site": "lt"} }appsettings.json 文件代码如下: {"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 组合快捷键快捷键总结 相关设置 设置撤回次数 自动保存 图片压缩 字体嵌入:目的是在不同的电脑上保留已经设置好的字体 多格式导出 (1)可以导出PDF (2)可以导…...
Java 语言关键字有哪些
Java 语言关键字有哪些 分类关键字访问控制privateprotectedpublic类,方法和变量修饰符abstractclassextendsfinalimplementsinterfacenativenewstaticstrictfpsynchronizedtransientvolatileenum程序控制breakcontinuereturndowhileifelseforinstanceofswitchcase…...
Go vs Rust:文件上传性能比较
在本文中,主要测试并比较了Go—Gin和Rust—Actix之间的多部分文件上传性能。 设置 所有测试都在配备16G内存的 MacBook Pro M1 上执行。 软件版本为: Go v1.20.5Rust v1.70.0 测试工具是一个基于 libcurl 并使用标准线程的自定义工具,能…...
C# NAudio 音频库
C# NAudio 音频库 NAudio安装NAudio简述简单示例1录制麦克风录制系统声卡WAV格式播放MP3格式播放AudioFileReader读取播放音频MediaFoundationReader 读取播放音频 NAudio安装 项目>NuGet包管理器 搜索NAudio点击安装,自动安装依赖库。 安装成功后工具箱会新增…...
springcloudalibaba-3
一、Nacos Config入门 1. 搭建nacos环境【使用现有的nacos环境即可】 使用之前的即可 2. 在微服务中引入nacos的依赖 <!-- nacos配置依赖 --><dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-…...
异步复位同步释放与同步复位打拍
参考链接:复位系列之异步复位同步释放与同步复位打拍...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
