当前位置: 首页 > news >正文

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.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000

解法

算法原理讲解

我们这题使用动态规划,我们做这类题目可以分为以下五个步骤

  1. 状态显示
  2. 状态转移方程
  3. 初始化(防止填表时不越界)
  4. 填表顺序
  5. 返回值
  • 状态显示
  1. 这道题如果我们和以前的题目一样定义成:从起点开始,到达 [i, j] 位置的时候,所需的最低初始健康点数。 那么我们分析状态转移的时候会有⼀个问题:那就是我们当前的健康点数还会受到后⾯的路径的影响。也就是从上往下的状态转移不能很好地解决问题。
  2. 这个时候我们要换⼀种状态表示:从 [i, j] 位置出发,到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候,后续的最佳状态就已经知晓。 综上所述,定义状态表示为: dp[i][j] 表示:从 [i, j] 位置出发,到达终点时所需的最低初始健康点数。
  • 状态转移方程
对于 dp[i][j] ,从 [i, j] 位置出发,下⼀步会有两种选择(为了⽅便理解,设 dp[ i ][ j ] 的最终答案是 x
  • 走到右边,然后⾛向终点 。那么我们在 [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]
综上所述,我们需要的是两种情况下的最⼩值,因此可得状态转移⽅程为:
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
但是,如果当前位置的 dungeon[i][j] 是⼀个⽐较⼤的正数的话, dp[i][j] 的值可能变成 0 或者负数。也就是最低点数会⼩于 1 ,那么骑⼠就会死亡。因此我们求出来的 dp[i][j] 如果⼩于等于 0 的话,说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i][j] 与 1 取⼀个最⼤值即可: dp[i][j] = max(1, dp[i][j])。
  • 初始化(防止填表时不越界)
dp 表最后⾯添加⼀⾏,并且添加⼀列后,所有的值都先初始化为⽆穷⼤,然后让 dp[m][n - 1] = dp[m - 1][n] = 1 即可。
  • 填表顺序
根据「状态转移⽅程」,我们需要「从下往上填每⼀⾏」,「每⼀⾏从右往左」。
  • 返回值
根据「状态表⽰」,我们需要返回 dp[0][0] 的值。

代码实现

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刷题--- 地下城游戏

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 ​​​​​​http://t.csdnimg.cn/6AbpV 数据结构与算法 ​​​http://t.csdnimg.cn/hKh2l 前言&#xff1a;这个专栏主要讲述动…...

【sklearn练习】鸢尾花

一、 import numpy as np from sklearn import datasets from sklearn.model_selection import train_test_split from sklearn.neighbors import KNeighborsClassifier 第二行&#xff1a;导入datasets数据集 第三行&#xff1a;train_test_split 的作用是将数据集随机分配…...

STM32的USB设备库

适用范围&#xff1a;“on the STM32F10xxx,STM32F37xxx, STM32F30xxx and STM32L15xxx devices.” STM32_USB-FS-Device_Lib_V4.0.0.rar&#xff08;访问密码&#xff1a;1666&#xff09;https://url48.ctfile.com/f/33868548-1000799917-a5409d?p1666 适用范围&#xff1…...

整数对最小和(100%用例)C卷 (JavaPythonC++Node.jsC语言)

给定两个整数数组 array1 、 array2 ,数组元素按升序排列。假设从 array1 、 array2 中分别取出一个元素可构成一对元素,现在需要取出 k 对元素,并对取出的所有元素求和,计算和的最小值 注意:两对元素如果对应于 array1 、 array2 中的两个下标均相同,则视为同一对元素。…...

QT笔记 - 加载带有提升为自定义部件类的“.ui“文件 - 重写QUiLoader::createWidget()函数

说明 如果ui设计中有提升过小部件&#xff0c;则无法直接使用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 设计应用&#xff1b;从sqlite获取、保存、删除数据&#xff1b;sqlite数据预填充功能&#xff1b;使用 RecyclerView 展示数据列表&#xff1b; 2. 使用架构组件 架构组…...

leetcode 动态规划(最后一块石头的重量II、目标和、一和零)

1049.最后一块石头的重量II 力扣题目链接(opens new window) 题目难度&#xff1a;中等 有一堆石头&#xff0c;每块石头的重量都是正整数。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 x < …...

JavaWeb-HTTP

一、概念 HTTP&#xff1a;HyperText Transfer Protocol&#xff0c;超文本传输协议。读者应该不是第一次接触这个名词&#xff0c;但可能仍然不是很理解&#xff0c;笔者将逐一解释。 HyperText&#xff08;超文本&#xff09;&#xff1a;根据维斯百科&#xff0c;Hypertex…...

算法训练营第四十二天|动态规划:01背包理论基础 416. 分割等和子集

目录 动态规划&#xff1a;01背包理论基础416. 分割等和子集 动态规划&#xff1a;01背包理论基础 文章链接&#xff1a;代码随想录 题目链接&#xff1a;卡码网&#xff1a;46. 携带研究材料 01背包问题 二维数组解法&#xff1a; #include <bits/stdc.h> using namesp…...

前端 JS篇快问快答

问题&#xff1a;常见的特殊字符&#xff08;不包括空格\s&#xff09; 正则表达式为&#xff1a; 回答&#xff1a;/[!#$%^&*()\-_{};:",.<>/?[\]~|]/ &#xff08;加粗的紫色字符都是特殊字符&#xff09; 问题&#xff1a;常见的特殊字符&#xff08;包括…...

vue/vue3/js来动态修改我们的界面浏览器上面的文字和图标

前言&#xff1a; 整理vue/vue3项目中修改界面浏览器上面的文字和图标的方法。 效果&#xff1a; vue2/vue3: 默认修改 public/index.html index.html <!DOCTYPE html> <html lang"en"><head><link rel"icon" type"image/sv…...

MobaXterm SSH 免密登录配置

文章目录 1.简介2.SSH 免密登录配置第一步&#xff1a;点击 Session第二步&#xff1a;选择 SSH第三步&#xff1a;输入服务器地址与用户名第四步&#xff1a;设置会话名称第五步&#xff1a;点击 OK 并输入密码 3.密码管理4.小结参考文献 1.简介 MobaXterm 是一个功能强大的终…...

霍兰德职业兴趣测试:找到与你性格匹配的职业

霍兰德职业兴趣理论 约翰霍兰德&#xff08;John Holland&#xff09;是美国约翰霍普金斯大学心理学教授&#xff0c;美国著名的职业指导专家。他于1959年提出了具有广泛社会影响的职业兴趣理论。认为人的人格类型、兴趣与职业密切相关&#xff0c;兴趣是人们活动的巨大动力&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函数时&#xff0c;发现运行时间太长了&#xff0c;如果使用视频流进行重映射时根本不能实时&#xff0c;因此只能加速 1.使用opencv里的cv::cuda::remap函数 cv::cuda::remap函数头文件是#include <opencv2/cudawarping.hpp>&#xff0c;编译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&#xff0c;顺带记录下笔记。 Elasticsearch依赖包版本 <properties><elasticsearch.version>7.9.3</elasticsearch.version><elasticsearch.rest.version>7.9.3</elasticsearch.rest.version> </propertie…...

[足式机器人]Part2 Dr. CAN学习笔记 - Ch02动态系统建模与分析

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记 - Ch02动态系统建模与分析 1. 课程介绍2. 电路系统建模、基尔霍夫定律3. 流体系统建模4. 拉普拉斯变换&#xff08;Laplace&#xff09;传递函数、微分方程4.1 Laplace Transform 拉式变换4.2 收…...

【一周年创作总结】人生是远方的无尽旷野呀

那一眼瞥见的伟大的灵魂&#xff0c;却似模糊的你和我 文章目录 &#x1f4d2;各个阶段的experience&#x1f50e;大一寒假&#x1f50e;大一下学期&#x1f50e;大一暑假&#x1f50e;大二上学期&#xff08;现在&#xff09; &#x1f354;相遇CSDN&#x1f6f8;自媒体&#…...

金融帝国实验室(Capitalism Lab)V10版本游戏平衡性优化与改进

即将推出的V10版本中的各种游戏平衡性优化与改进&#xff1a; ————————————— 一、当玩家被提议收购一家即将破产的公司时&#xff0c;显示商业秘密。 当一家公司濒临破产&#xff0c;玩家被提议收购该公司时&#xff0c;如果玩家有兴趣评估该公司&#xff0c;则无…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...