代码随想录算法训练营第三十九天【动态规划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-…...
异步复位同步释放与同步复位打拍
参考链接:复位系列之异步复位同步释放与同步复位打拍...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
