LeetCode刷题--- 地下城游戏
个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
http://t.csdnimg.cn/yUl2I
【C++】
http://t.csdnimg.cn/6AbpV
数据结构与算法
http://t.csdnimg.cn/hKh2l
前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
地下城游戏
题目链接:地下城游戏
题目
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1:

输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出:7 解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。
示例 2:
输入:dungeon = [[0]] 输出:1
提示:
m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000
解法
算法原理讲解
我们这题使用动态规划,我们做这类题目可以分为以下五个步骤
- 状态显示
- 状态转移方程
- 初始化(防止填表时不越界)
- 填表顺序
- 返回值
- 状态显示
- 这道题如果我们和以前的题目一样定义成:从起点开始,到达 [i, j] 位置的时候,所需的最低初始健康点数。 那么我们分析状态转移的时候会有⼀个问题:那就是我们当前的健康点数还会受到后⾯的路径的影响。也就是从上往下的状态转移不能很好地解决问题。
- 这个时候我们要换⼀种状态表示:从 [i, j] 位置出发,到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候,后续的最佳状态就已经知晓。 综上所述,定义状态表示为: dp[i][j] 表示:从 [i, j] 位置出发,到达终点时所需的最低初始健康点数。
- 状态转移方程
- 走到右边,然后⾛向终点 。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要大于等于右边位 置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i][j + 1] 。 通过移项可得: x >= dp[i][j + 1] - dungeon[i][j] 。因为我们要的是最小值,因此这种情况下的 x = dp[i][j + 1] - dungeon[i][j] ;
- ⾛到下边,然后⾛向终点。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要⼤于等于下边位置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i + 1][j] 。 通过移项可得: x >= dp[i + 1][j] - dungeon[i][j] 。因为我们要的是最小值,因此这种情况下的 x = dp[i + 1][j] -dungeon[i][j] ;
- 初始化(防止填表时不越界)
- 填表顺序
- 返回值
代码实现
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size();int 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];}
};
相关文章:
LeetCode刷题--- 地下城游戏
个人主页:元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 http://t.csdnimg.cn/6AbpV 数据结构与算法 http://t.csdnimg.cn/hKh2l 前言:这个专栏主要讲述动…...
【sklearn练习】鸢尾花
一、 import numpy as np from sklearn import datasets from sklearn.model_selection import train_test_split from sklearn.neighbors import KNeighborsClassifier 第二行:导入datasets数据集 第三行:train_test_split 的作用是将数据集随机分配…...
STM32的USB设备库
适用范围:“on the STM32F10xxx,STM32F37xxx, STM32F30xxx and STM32L15xxx devices.” STM32_USB-FS-Device_Lib_V4.0.0.rar(访问密码:1666)https://url48.ctfile.com/f/33868548-1000799917-a5409d?p1666 适用范围࿱…...
整数对最小和(100%用例)C卷 (JavaPythonC++Node.jsC语言)
给定两个整数数组 array1 、 array2 ,数组元素按升序排列。假设从 array1 、 array2 中分别取出一个元素可构成一对元素,现在需要取出 k 对元素,并对取出的所有元素求和,计算和的最小值 注意:两对元素如果对应于 array1 、 array2 中的两个下标均相同,则视为同一对元素。…...
QT笔记 - 加载带有提升为自定义部件类的“.ui“文件 - 重写QUiLoader::createWidget()函数
说明 如果ui设计中有提升过小部件,则无法直接使用QUiLoader加载。完成加载需要重新实现UiLoader::createWidget()函数。 函数 virtual QWidget * QUiLoader::createWidget(const QString & className, QWidget * parent Q_NULLPTR, const QString & name…...
开启Android学习之旅-2-架构组件实现数据列表及添加(kotlin)
Android Jetpack 体验-官方codelab 1. 实现功能 使用 Jetpack 架构组件 Room、ViewModel 和 LiveData 设计应用;从sqlite获取、保存、删除数据;sqlite数据预填充功能;使用 RecyclerView 展示数据列表; 2. 使用架构组件 架构组…...
leetcode 动态规划(最后一块石头的重量II、目标和、一和零)
1049.最后一块石头的重量II 力扣题目链接(opens new window) 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < …...
JavaWeb-HTTP
一、概念 HTTP:HyperText Transfer Protocol,超文本传输协议。读者应该不是第一次接触这个名词,但可能仍然不是很理解,笔者将逐一解释。 HyperText(超文本):根据维斯百科,Hypertex…...
算法训练营第四十二天|动态规划:01背包理论基础 416. 分割等和子集
目录 动态规划:01背包理论基础416. 分割等和子集 动态规划:01背包理论基础 文章链接:代码随想录 题目链接:卡码网:46. 携带研究材料 01背包问题 二维数组解法: #include <bits/stdc.h> using namesp…...
前端 JS篇快问快答
问题:常见的特殊字符(不包括空格\s) 正则表达式为: 回答:/[!#$%^&*()\-_{};:",.<>/?[\]~|]/ (加粗的紫色字符都是特殊字符) 问题:常见的特殊字符(包括…...
vue/vue3/js来动态修改我们的界面浏览器上面的文字和图标
前言: 整理vue/vue3项目中修改界面浏览器上面的文字和图标的方法。 效果: vue2/vue3: 默认修改 public/index.html index.html <!DOCTYPE html> <html lang"en"><head><link rel"icon" type"image/sv…...
MobaXterm SSH 免密登录配置
文章目录 1.简介2.SSH 免密登录配置第一步:点击 Session第二步:选择 SSH第三步:输入服务器地址与用户名第四步:设置会话名称第五步:点击 OK 并输入密码 3.密码管理4.小结参考文献 1.简介 MobaXterm 是一个功能强大的终…...
霍兰德职业兴趣测试:找到与你性格匹配的职业
霍兰德职业兴趣理论 约翰霍兰德(John Holland)是美国约翰霍普金斯大学心理学教授,美国著名的职业指导专家。他于1959年提出了具有广泛社会影响的职业兴趣理论。认为人的人格类型、兴趣与职业密切相关,兴趣是人们活动的巨大动力&a…...
LVGL学习笔记 显示和隐藏 对象的属性标志位 配置
在显示GUI的过程中需要对某些对象进行临时隐藏或临时显示,因此需要对该对象的FLAG进行配置就可以实现对象的显示和隐藏了. 调用如下接口可以实现: lv_obj_add_flag(user_obj, LV_OBJ_FLAG_HIDDEN);//隐藏对象lv_obj_clear_flag(user_obj, LV_OBJ_FLAG_HIDDEN);//取消隐藏实现的…...
cuda上使用remap函数
在使用opencv中的remap函数时,发现运行时间太长了,如果使用视频流进行重映射时根本不能实时,因此只能加速 1.使用opencv里的cv::cuda::remap函数 cv::cuda::remap函数头文件是#include <opencv2/cudawarping.hpp>,编译ope…...
【JaveWeb教程】(18) MySQL数据库开发之 MySQL数据库设计-DDL 如何查询、创建、使用、删除数据库数据表 详细代码示例讲解
目录 2. 数据库设计-DDL2.1 项目开发流程2.2 数据库操作2.2.1 查询数据库2.2.2 创建数据库2.2.3 使用数据库2.2.4 删除数据库 2.3 图形化工具2.3.1 介绍2.3.2 安装2.3.3 使用2.2.3.1 连接数据库2.2.3.2 操作数据库 2.3 表操作2.3.1 创建2.3.1.1 语法2.3.1.2 约束2.3.1.3 数据类…...
ElasticSearch学习笔记-SpringBoot整合Elasticsearch7
项目最近需要接入Elasticsearch7,顺带记录下笔记。 Elasticsearch依赖包版本 <properties><elasticsearch.version>7.9.3</elasticsearch.version><elasticsearch.rest.version>7.9.3</elasticsearch.rest.version> </propertie…...
[足式机器人]Part2 Dr. CAN学习笔记 - Ch02动态系统建模与分析
本文仅供学习使用 本文参考: B站:DR_CAN Dr. CAN学习笔记 - Ch02动态系统建模与分析 1. 课程介绍2. 电路系统建模、基尔霍夫定律3. 流体系统建模4. 拉普拉斯变换(Laplace)传递函数、微分方程4.1 Laplace Transform 拉式变换4.2 收…...
【一周年创作总结】人生是远方的无尽旷野呀
那一眼瞥见的伟大的灵魂,却似模糊的你和我 文章目录 📒各个阶段的experience🔎大一寒假🔎大一下学期🔎大一暑假🔎大二上学期(现在) 🍔相遇CSDN🛸自媒体&#…...
金融帝国实验室(Capitalism Lab)V10版本游戏平衡性优化与改进
即将推出的V10版本中的各种游戏平衡性优化与改进: ————————————— 一、当玩家被提议收购一家即将破产的公司时,显示商业秘密。 当一家公司濒临破产,玩家被提议收购该公司时,如果玩家有兴趣评估该公司,则无…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
