C++ 路径问题

news/2024/4/15 5:04:33/文章来源:https://blog.csdn.net/m0_74922218/article/details/136505971

目录

例1

例2

例3

例4

例5

例6


例1

62. 不同路径

 

1.初始化

2.当前位置的条数,就是上面位置的条数 ,加上其左边位置的条数,dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

参考代码

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1));dp[0][1] = 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][n];}
};

例2

63. 不同路径 II

1.初始化dp

2.将obstacleGrid中为0 的值映射到dp表中为0即可

参考代码

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));dp[0][1] = 1;for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)if(obstacleGrid[i - 1][j - 1] == 0)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m][n]; }
};

例3

LCR 166. 珠宝的最高价值

初始化默认为0,且题目中说了,价值都是大于0

因为是求右下角的值,那么dp就是从左上往右下

参考代码

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size(), n = frame[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];return dp[m][n];}
};

例4

931. 下降路径最小和

注意:如果没有这一行for(int i = 0; i < n + 2; i++) dp[0][i] = 0;会溢出,如果改成longlong的vector,那么这时候min会出现没有匹配的模版,因为类型不同,并不是min写错了,官方文档

参考代码

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));for(int i = 0; i < n + 2; i++) dp[0][i] = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];int ret = INT_MAX;for(int i = 1; i <= n; i++)ret = min(ret, dp[n][i]);//没有int和long long 的比较return ret;}
};

例5

64. 最小路径和

 最小:::初始化为INT_MAX;

dp[0][1] = 0方便dp[1][1]

映射

参考代码

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));dp[0][1] = 0;for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];return dp[m][n];}
};

例6

174. 地下城游戏

 求的是dp[0][0],那么就是从左下往右上填写dp表

这里不用映射

dp表里的值代表的是+-之后的血量,dp[m][n - 1] = dp[m - 1][n] = 1;这一步代表走到这俩位置还能保持一格血,这俩位置不会+-血,也就是 +- 完dp[m - 1][n - 1]后还剩下1滴血

 dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];等价于:当前需要的血量 = 下一步较小的血量 - 需要+-的血量,如果所需是0,则改成1

参考代码

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));dp[m][n - 1] = dp[m - 1][n] = 1;for(int i = m - 1; i >= 0; i--)for(int j = n - 1; j >= 0; j--){dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]);}return dp[0][0];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_996847.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Material UI 5 学习01-按钮组件

Material UI 5 学习01-按钮组件 一、安装Material UI二、 组件1、Button组件1、基础按钮2、variant属性3、禁用按钮4、可跳转的按钮5、disableElevation属性6、按钮的点击事件onClick 2、Button按钮的颜色和尺寸1、Button按钮的颜色2、按钮自定义颜色3、Button按钮的尺寸 3、图…

VUE3中ArcGIS JsAPI 4.27 Map 隐藏地图黑色边框

问题&#xff1a; vue3中引入arcgis jsapi 地图加载后&#xff0c;点击地图会出现黑色边框&#xff0c;看起来很不协调 解决方案&#xff1a; 新建自定义CSS文件&#xff0c;输入一下样式内容&#xff0c;并在vue页面直接用import引入即可。 注意&#xff1a;直接写到vue页面…

Golang Channel 详细原理和使用技巧

1.简介 Channel(一般简写为 chan) 管道提供了一种机制:它在两个并发执行的协程之间进行同步&#xff0c;并通过传递与该管道元素类型相符的值来进行通信,它是Golang在语言层面提供的goroutine间的通信方式.通过Channel在不同的 goroutine中交换数据&#xff0c;在goroutine之间…

3Dmax中VR渲染太阳光渲染参数怎么设置?渲染100云渲染助力

我们用3Dmax建模时一些场景会用到太阳光&#xff0c;那么渲染参数是如何设置的呢&#xff1f; 我们一起来看看&#xff0c;直接上图 以上就是详细的参数设置&#xff0c;大家可以用做参考&#xff0c;如果本地渲染慢的朋友可以考虑使用云渲染100 机器多&#xff0c;渲染稳定不…

YOLOSHOW - YOLOv5 / YOLOv7 / YOLOv8 / YOLOv9 基于 Pyside6 的图形化界面

YOLOSHOW 是一个基于 PySide6&#xff08;Qt for Python&#xff09;开发的图形化界面应用程序&#xff0c;主要用于集成和可视化YOLO系列&#xff08;包括但不限于YOLOv5、YOLOv7、YOLOv8、YOLOv9&#xff09;的目标检测模型。YOLOSHOW 提供了一个用户友好的交互界面&#xff…

一文详解:Open SSL

Open SSL是 SSL (传输层安全)和 TLS (传输层安全)协议的健壮的开源实现。这些加密协议被广泛用于保护计算机网络上的通信&#xff0c;通过在两个通信应用程序之间提供隐私和数据完整性。从更实际的角度来说&#xff0c;OpenSSL 是一个工具包&#xff0c;其中包含各种命令行实用…

JavaScript中call和apply函数方法

看下下面这个代码示例&#xff1a; javascript const lufthansa {airline: Lufthansa,iataCode: LH,bookings: [],book(flightNum, name) {console.log(${name} booked a seat on ${this.airline} flight ${this.iataCode}${flightNum});}, };lufthansa.book(239, ‘IT知识一…

力扣--动态规划152.乘积最大子数组

思路分析&#xff1a; 使用动态规划&#xff0c;定义一个二维数组dp&#xff0c;其中dp[i][0]表示以第i个元素结尾的乘积最大子数组的乘积&#xff0c;dp[i][1]表示以第i个元素结尾的乘积最小子数组的乘积。初始化dp数组的第一个元素为数组的第一个元素。遍历数组&#xff0c;…

Unity背景模糊图片高斯模糊高性能的实现方案

环境&#xff1a; unity2021.3.x 效果&#xff1a; 模糊前&#xff1a; 模糊后&#xff1a; 模糊前&#xff1a; 模糊后&#xff1a; 实现核心思路(shader)&#xff1a; SubShader {CGINCLUDE#include "UnityCG.cginc"sampler2D _MainTex; // 主纹理half4 _MainTe…

持续集成(CICD)- Jenkins安装插件

文章目录 Jenkins 检查自己是否有此插件安装插件&#xff1a; 以Git 插件举例&#xff08;其他插件类似&#xff09;&#xff1a; Jenkins 检查自己是否有此插件 检查自己的jenkins是否有git插件&#xff1a;进入Manage Jenkins - 往下滑动找到Global Tool Configuration - 如…

Android使用OpenGL和FreeType绘制文字

Open GL主要是渲染图形的&#xff0c;有时候需要绘制文字&#xff0c;网上搜了一下&#xff0c;基本思路都是把文字转成位图&#xff0c;再使用Open GL纹理进行渲染。为了保证灵活性&#xff0c;我们把每个可能用到的字符都生成一个位图加载到纹理缓冲区&#xff0c;绘制字符串…

未来AI发展趋势

引言 如何实现一个乌托邦式的社会呢&#xff1f;如果直接将人类社会分为两个阵营&#xff0c;一个是以旧人类为首的阵营&#xff0c;一个是以AI抚养的新人类阵营&#xff0c;其中新人类阵营的所有资源皆由旧人类阵营提供&#xff0c;且旧人类阵营的人类都经过了化学阉割无法生…

Linux CentOS系统安装Spug并结合内网穿透实现远程访问本地运维平台

目录 前言 1. Docker安装Spug 2 . 本地访问测试 3. Linux 安装cpolar 4. 配置Spug公网访问地址 5. 公网远程访问Spug管理界面 6. 固定Spug公网地址 结语 作者简介&#xff1a; 懒大王敲代码&#xff0c;计算机专业应届生 今天给大家聊聊Linux CentOS系统安装Spug并结合…

【实验】学习实验debug,以及经验感悟

记录两次独立解决问题的过程&#xff1a; 目前来看&#xff0c;问题分为几种&#xff1a; 抄代码的时候抄错了&#xff0c;比如dim1写成dim0这种 逻辑错误&#xff0c;如果两份代码没什么差别的话&#xff0c;那么肯定是逻辑错误。 下面的两个问题都是逻辑错误&#xff0c;因为…

2024最新算法:斑翠鸟优化算法(Pied Kingfisher Optimizer ,PKO)求解23个基准函数

一、斑翠鸟优化算法 斑翠鸟优化算法&#xff08;Pied Kingfisher Optimizer ,PKO&#xff09;&#xff0c;是由Abdelazim Hussien于2024年提出的一种基于群体的新型元启发式算法&#xff0c;它从自然界中观察到的斑翠鸟独特的狩猎行为和共生关系中汲取灵感。PKO 算法围绕三个不…

FPGA- RGB_TFT显示屏原理及驱动逻辑

下图是TFT显示屏的显示效果 该显示屏共分为 2 个版本&#xff0c;4.3 寸版本的 TFT4.3’’_V3.0 和 5.0 寸版本的 TFT5.0’’_V3.0。 两者 PCB 背板电路完全相同&#xff0c;接口脚位定义完全相同&#xff0c;接口时序完全相同&#xff0c;仅使用的显示屏 模组尺寸不同。设计两…

uniapp直接连接wifi(含有ios和安卓的注意事项)

前言 小程序中直接连接wifi-----微信小程序 代码 启动 //启动wifistartWifi() {return new Promise((resolve, reject) > {uni.startWifi({success: (res) > {console.log(启动wifi 成功, res)resolve(true)},fail: (err) > {console.error(启动wifi 失败, err)uni.s…

【Web安全】XSS攻击与绕过

【Web安全】XSS攻击与绕过 【Web安全靶场】xss-labs-master 1-20 文章目录 【Web安全】XSS攻击与绕过1. XSS攻击是啥&#xff1f;2. XSS如何发生&#xff1f;3. XSS分类3.1. 反射型3.2. 存储型3.3. DOM型 4. XSS攻击方式1. script标签2. img标签3. input标签4. details标签5.…

强化学习中动作价值函数和状态价值函数的联系区别?

在强化学习中&#xff0c;动作价值函数&#xff08;Q函数&#xff09;和状态价值函数&#xff08;V函数&#xff09;都是值函数&#xff0c;用于评估在不同状态或状态动作对下的值。它们之间存在联系&#xff0c;但有一些区别&#xff1a; 动作价值函数&#xff08;Q函数&#…

MySQL 学习笔记(基础篇 Day2)

「写在前面」 本文为黑马程序员 MySQL 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。推荐先按顺序阅读往期内容&#xff1a; 1. MySQL 学习笔记&#xff08;基础篇 Day1&#xff09; 目录 3 函数 3.1 字符串函数 3…