C++--动态规划路径问题
1.不同路径 力扣
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/unique-paths-ii
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int r=obstacleGrid.size();int l=obstacleGrid[0].size();vector<vector<int>> dp(r+1,vector<int>(l+1));dp[1][0]=1;for(int i=1;i<=r;i++){for(int j=1;j<=l;j++){if(obstacleGrid[i-1][j-1]==0){dp[i][j]=dp[i][j-1]+dp[i-1][j]; }else {dp[i][j]=0;}}}return dp[r][l];}
};
2.不同路径 力扣
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7
输出:28示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下示例 3:
输入:m = 7, n = 3
输出:28示例 4:
输入:m = 3, n = 3
输出:6来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/unique-paths
class Solution {
public:int uniquePaths(int m, int n) {//以某一处为结尾,创建dp表vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化dp表//dp[0][1]=1;dp[1][0]=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];}
};
3.礼物的最大价值 力扣
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof
class Solution {
public:int maxValue(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();vector<vector<int>> arr(m+1,vector<int>(n+1));//初始化,求最大,所以初始化最小,vector默认初始//化为0for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){arr[i][j]=max(arr[i-1][j],arr[i][j-1])+grid[i-1][j-1];//递推公式}}return arr[m][n];}
};
4.下降路径最小和 力扣
给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1:
输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:如图所示,为和最小的两条下降路径示例 2:
输入:matrix = [[-19,57],[-40,-5]]
输出:-59
解释:如图所示,为和最小的下降路径来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-falling-path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
5.最小路径和 力扣
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-path-sum
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));//创建dp表,并初始化为最大值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=0;i<=n;i++)ret=min(ret,dp[n][i]);//找最小return ret;}
};
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int r=grid.size();int l=grid[0].size();vector<vector<int>> dp(r+1,vector<int>(l+1,INT_MAX));//创建dp表,并初始化,找最小,初始化为最大dp[0][1]=dp[1][0]=0;//由于有两种走法,所以要求drid[0][0]的上方和左边的为最小数0for(int i=1;i<=r;i++){for(int j=1;j<=l;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];//地推公式}}return dp[r][l];//返回值}
};
6.地下城游戏 力扣
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1:
输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出:7
解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。示例 2:
输入:dungeon = [[0]]
输出:1来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/dungeon-game
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int r=dungeon.size();int l=dungeon[0].size();vector<vector<int>> dp(r+1,vector<int>(l+1,INT_MAX));//创建dp表+初始化dp[r][l - 1] = dp[r - 1][l] = 1;for(int i=r-1;i>=0;i--){for(int j=l-1;j>=0;j--){dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];//填表+递推公式if(dp[i][j]<=0)dp[i][j]=1;}}return dp[0][0];//返回值}
}
相关文章:
C++--动态规划路径问题
1.不同路径 力扣 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。那么从…...
从实践彻底掌握MySQL的主从复制
目录 一、本次所用结构如图---一主多从级联: 二、IP。 三、配置M1: 四、从库M1S1: 五、从库M2配置: 六、 从库M2S1: 一、本次所用结构如图--- 一主多从级联: 二、IP。这里M1S1和M1S2一样的࿰…...
机器学习深度学习——线性回归的基本元素
回归用来表示输入输出之间的关系。 用实际例子来解释一下线性回归:根据房屋的面积、房龄来估算房屋价格。为了实现这个预测放假的模型,需要收集一个真实的数据集,该数据集包括了房屋的销售价格、面积和房龄。 在机器学习中,这个数…...
K8S初级入门系列之八-网络
一、前言 本章节我们将了解K8S的相关网络概念,包括K8S的网络通讯原理,以及Service以及相关的概念,包括Endpoint,EndpointSlice,Headless service,Ingress等。 二、网络通讯原理和实现 同一K8S集群&…...
分段@Transactional 坑及失效问题
Transactional 背景:在某些情况下,我们需要分段transaction,在最外面没有transaction,里面分成几个transaction,保证分段是成功的。 问题代码: Service public Order getOrder1(String id) {Optional<Or…...
25、matlab里面的10中优化方法介绍——Opt_Golden法(matlab程序)
1.简述 基本思想 黄金分割法也称为 0.618 法,其基本思想是通过取试探点和进行函数值比较,使包含极小点的搜索区间不断缩短以逼近极小值点。适用于确定区间上的任何单谷函数求极小值的问题。 公式推导 设有定义在[ a , b ] [a,b][a,b]上的单谷函数 φ ( …...
点云拟合球体
前言:在很多情况下,需要根据点云来拟合球体,本博文主要介绍各种方法的拟合情况及优缺点,希望对各位小伙伴有所帮助! 目录 1. vtkFitImplicitFunction进行球拟合 2. 四点求解球 1. vtkFitImplicitFunction进行球拟合 …...
基于动态规划(DP)算法的增程式EV能量管理策略研究(MATLAB编程)
文章目录 算法代码仿真结果结果分析算法代码 clc; clear; close all; load CWTVC.mat N=length(T_z); %N=200;load minFuelConsup.txt minFuel_Pe=minFuelConsup(:...
前端知识点视频补充
使用工具: Vscode使用: 需要下载插件:open in browser。这个插件可以快速打开浏览器。 选择文件夹有两种方式:选择打开文件、拖拽方式(这种最方便) 快捷键:快速生成Htm结构文件:…...
python多线程—终止子线程
总体思路 1、获取需要终止的子线程id 2、根据子线程id,终止子线程。 过程 获取子线程id: import threading Thread_id threading.get_ident() # 获取子线程的id值线程终止函数 def async_raise(Thread_id, exctype):"""raises th…...
#P1012. [NOIP2015提高组] 神奇的幻方
题目描述 幻方是一种很神奇的 N \times NNN 矩阵:它由数字 1,2,3, \ldots ,N \times N1,2,3,…,NN 构成,且每行、每列及两条对角线上的数字之和都相同。 当 NN 为奇数时,我们可以通过以下方法构建一个幻方: 首先将 11 写在第一行…...
(学习笔记-IP)Ping的工作原理
Ping是基于ICMP协议工作的,ICMP报文封装在IP包里面,它工作在网络层,是IP协议的助手。 ICMP包头的类型字段,大致可分为两大类: 一类是用于诊断的查询消息,也就是查询报文类型一类是通知出错原因的错误消息&…...
php 进程间通信:管道、uds
1、管道 1.1、管道概念 管道是单向的、先进先出的,它把进程的输出和另一个进程的输入连接在一起。一个进程往管道写入数据,另一个进程从管道读取数据。数据被从管道中读取出来之后,将被删除,其他进程无法在读取到相应的数据。管…...
Stable Diffusion如何生成高质量的图-prompt写法介绍
文章目录 Stable Diffusion使用尝试下效果prompt的编写技巧prompt 和 negative promptPrompt格式Prompt规则细节优化Guidance Scale 总结 Stable Diffusion Stable Diffusion是一个开源的图像生成AI系统,由Anthropic公司开发。它基于 Transformer模型架构,可以通过文字描述生成…...
MySQL 高级SQL语句(一)
目录 一、高级SQL语句(进阶查询) 1.1 select 1.2 distinct 1.3 where 1.4 and 和 or 1.5 in 1.6 between 1.7 通配符 1.8 like 1.9 order by 一、高级SQL语句(进阶查询) 先准备2个表 一个location表: use m…...
SkyWalking链路追踪-技术文档首页
SkyWalking 文档中文版(社区提供) (skyapm.github.io)https://skyapm.github.io/document-cn-translation-of-skywalking/ SkyWalking-基本概念 SkyWalking链路追踪是一个用于分布式系统的性能监控工具,它帮助开发人员了解系统中各组件之间…...
AndroidStudio Memory profiler(内存分析器)
1.Record Java/Kotlin allocations 查看java 层中对象的调用栈和短时间内创建对象的次数。可用于内存抖动快速分析,可用快速查找到该对象的调用栈(等同于mat) 从上图可见,短时间内创建了23个char[] 数组,其中最大的char[] 占用20k, 查看cll stack 调用…...
【C++模板进阶】
目录 一、模板使用时的一个小注意点二、非类型模板参数三、类模板的特化3.1函数模板的特化3.2类模板的特化3.2.1全特化3.2.2偏特化 四、模板的分离编译4.1模板不支持分离编译4.2模板分离编译报错的分析4.2解决方案 五、模板的总结 一、模板使用时的一个小注意点 在使用模板时&…...
(一)RabbitMQ概念-优势、劣势、应用场景 、AMQP、工作原理
Lison <dreamlison163.com>, v1.0.0, 2023.06.22 RabbitMQ概念-优势、劣势、应用场景 、AMQP、工作原理 文章目录 RabbitMQ概念-优势、劣势、应用场景 、AMQP、工作原理RabbitMQ概念RabbitMQ的优势RabbitMQ劣势RabbitMQ应用的场景RabbitMQ_AMQPRabbitMQ工作原理 RabbitM…...
JetBrains全家桶:如何自定义实现类TODO注释?
文章目录 效果图具体方法参考文献 效果图 TODO注释大家应该都用过,在注释开头打上TODO的话,软件下方的TODO选项卡里就可以自动筛选出你打了TODO的注释,你可以点击里面对应的注释来实现快速跳转。 jetbrains全家桶(如Pycharm、Int…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
深度解析云存储:概念、架构与应用实践
在数据爆炸式增长的时代,传统本地存储因容量限制、管理复杂等问题,已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性,成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理,云存储正重塑数据存储与…...
二维数组 行列混淆区分 js
二维数组定义 行 row:是“横着的一整行” 列 column:是“竖着的一整列” 在 JavaScript 里访问二维数组 grid[i][j] 表示 第i行第j列的元素 let grid [[1, 2, 3], // 第0行[4, 5, 6], // 第1行[7, 8, 9] // 第2行 ];// grid[i][j] 表示 第i行第j列的…...
