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版本中的各种游戏平衡性优化与改进: ————————————— 一、当玩家被提议收购一家即将破产的公司时,显示商业秘密。 当一家公司濒临破产,玩家被提议收购该公司时,如果玩家有兴趣评估该公司,则无…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
