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

详解LeetCode地下城游戏（动态规划）——区分两种状态表示形式

news 来源：原创 2025/7/12 6:46:24

地下城游戏

题目链接：174. 地下城游戏

状态表示：
按照以往题的表示，dp[i][j]表示：从起点（0，0）位置到达（i，j）位置时，所需的最小初始健康值。但是如果这么去表示，不仅要考虑到达（i，j）位置的最小初始健康值，由于魔法球的存在，还需要考虑到达（i，j）位置时的健康值，因为魔法球会对算后续位置的最小初始健康值产生影响

下面用题目中的示例1为例，演示:
在这里插入图片描述
由此可知，到达魔法球位置所需的最低初始健康值和上一次的最低初始健康值保持一致，而魔法球会增加健康值，这就会对后面的结果产生影响，因此我们不仅要考虑到达（i，j）位置的最小初始健康值，还需要考虑到达（i，j）位置时的健康值，以保证后续结果的正确性

因此，我们可以试着用dp[i][j]表示：以（i，j）位置为起点，到达终点位置时，所需的最小健康值。当(i,j)位置是魔法球时，可以用之前的dp[i+1][j]和dp[i][j+1]中的最小健康值减去治疗量，就能得到当前的位置到达终点位置时所需的最小健康值dp[i][j]（注意：dp[i][j]不能小于0，最小值为1)；当(i,j)位置是恶魔时，也是这样处理，实际上就是加上了需要扣除的健康值
在这里插入图片描述
通过这种状态表示，我们最终能够求得结果！

总结：

这道题的难点在于怎么去处理健康值增加的问题，健康值的增加不能为之前的损失提供帮助，只会对后续有帮助
如果按照第一种状态表示，dp[i][j]仅仅只表示了从（0，0）位置到达（i，j）位置所需的最小初始健康值，而由于魔法球的存在，导致后续的健康值会增加，因此我们还需要去记录当前位置的健康值，以保证后续计算最小初始健康值的正确性
如果按照第二种状态表示，dp[i][j]表示从（0，0）位置出发，按照最优路径到达（i，j）位置时，还需要剩余的最小健康值（为了到达终点后，健康值为1）。即dp[i][j]不仅表示了从（i，j）位置到达终点位置所需的最小初始健康值，还表示了从（0，0）位置出发到达（i，j）位置时，所需剩余的最小健康值（即当前健康值）
比较两种状态表示，可知，第二种表示更合理，更方便后续的填表

状态转移方程
dp[i][j] = min(dp[i+1][j],dp[i][j+1])-d[i][j]，dp[i][j] = max(1, dp[i][j])

初始化
创建表时，多创建一行(第m行)和一列（第n列），除dp[m][n-1] = 1（dp[m-1][n] 也可初始化为1，表示救出公主后还需剩余1点健康值），其他都初始化为正无穷(以防对填表产生影响)

填表顺序
从下往上，每一行从右往左

返回值
dp[0][0]

实现代码

class Solution {public int calculateMinimumHP(int[][] dungeon) {//1.创建dp表int m = dungeon.length;int n = dungeon[0].length;int[][] dp = new int[m+1][n+1];//2.初始化for(int row = 0; row < m+1; row++) {dp[row][n] = Integer.MAX_VALUE;}for(int col = 0; col < n+1; col++) {dp[m][col] = Integer.MAX_VALUE;}dp[m][n-1] = 1;//3.填表for(int i = m-1; i >= 0; i--) {for(int j = n-1; j >= 0; j--) {dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];dp[i][j] = Math.max(1, dp[i][j]);}}//4.返回值return dp[0][0];}
}

详解LeetCode地下城游戏（动态规划）——区分两种状态表示形式

地下城游戏题目链接：174. 地下城游戏状态表示： 按照以往题的表示，dp[i][j]表示：从起点（0，0）位置到达（i，j）位置时，所需的最小初始健康值。但是…...

编程日记 2025/7/12 6:46:24

CV(3)--噪声滤波和特征

前言仅记录学习过程，有问题欢迎讨论图像噪声（需要主动干扰的场景）： 添加高斯噪声：概率密度函数服从高斯分布的一类噪声通过设置sigma和mean生成符合高斯分布的随机数，然后计算输出像素，放缩…...

编程日记 2025/7/12 23:40:27

[C++]常对象、常对象成员、指向对象的常指针、指向常对象的指针变量以及对象的常引用

一、常对象 1.定义： 一个常对象就是声明为常量的对象。我们不能改变这个对象的任何成员数据。具体来说，它是通过const关键字来声明的。 2.语法格式： const 类名对象名;3.代码示例： class MyClass { public:int x;void setX…...

编程日记 2025/7/9 1:26:57

Spring Boot微服务应用实战：构建高效、可扩展的服务架构

在当今的软件开发领域，微服务架构凭借其高度的灵活性、可扩展性和可靠性，已成为众多企业的首选。而Spring Boot，作为Spring框架的一个子项目，以其简洁的API、快速的应用启动以及内嵌的Servlet容器等特点，成为了构建微服…...

编程日记 2025/7/10 16:19:39

如何通过 Windows 自带的启动管理功能优化电脑启动程序

在日常使用电脑的过程中，您可能注意到开机后某些程序会自动运行。这些程序被称为“自启动”或“启动项”，它们可以在系统启动时自动加载并开始运行，有时甚至在后台默默工作。虽然一些启动项可能是必要的（如杀毒软件）&a…...

编程日记 2025/7/7 2:29:56

力扣每日一题 - 1812. 判断国际象棋棋盘中一个格子的颜色

题目还需要你前往力扣官网查看详细的题目要求地址 1.给你一个坐标 coordinates ，它是一个字符串，表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。2.如果所给格子的颜色是白色，请你返回 true，如果是黑色&#xff…...

编程日记 2025/7/8 3:50:52

Python subprocess.run 使用注意事项，避免出现list index out of range

在执行iOS UI 自动化专项测试的时候，在运行第一遍的时候遇到了这样的错误： 2024-12-04 20:22:27 ERROR conftest pytest_runtest_makereport 106 Test test_open_stream.py::TestOpenStream::test_xxx_open_stream[iPhoneX-xxx-1-250] failed with err…...

编程日记 2025/7/7 20:11:37

UI自动化测试框架：PO模式+数据驱动

🍅 点击文末小卡片，免费获取软件测试全套资料，资料在手，涨薪更快 1. PO 设计模式简介什么是 PO 模式？ PO（PageObject）设计模式将某个页面的所有元素对象定位和对元素对象的操作封装成一个 Pa…...

编程日记 2025/7/9 20:28:17

第四十六篇 Vision Transformer论文翻译

论文连接：https://arxiv.org/abs/2010.11929 GitHub：https://github.com/google-research/vision_transformer 摘要虽然Transformer架构已成为自然语言处理任务的实际标准，但其在计算机视觉中的应用仍然有限。在计算机视觉中，注意力机制要么与卷积网络结合使用，要么在保…...

编程日记 2025/7/3 19:13:54

如何在Ubuntu中利用repo和git地址下载获取imx6ull的BSP

01-设置git的用户名和邮箱 git config --global user.name "suwenhao" git config --global user.email "2487872782qq.com"这里不设置的话后面在第5步的repo配置中还是会要求输入，而且以后进行相关操作都要输入，不妨现在就进行配置…...

编程日记 2025/7/10 19:27:13

redis数据结构和内部编码及单线程架构

博主主页: 码农派大星. 数据结构专栏:Java数据结构数据库专栏:数据库 JavaEE专栏:JavaEE 软件测试专栏:软件测试关注博主带你了解更多知识 1. 数据结构和内部编码 Redis会在合适的场景选择合适的内部编码我们可以通过objectencoding命令查询内部编码 : 2. 单线程架构 …...

编程日记 2025/7/3 19:15:46

2412d,d的6月会议

信息:gtkD的文档位置原文总结 DMDARM后端 Razvan问Walter他对DMD的ARM后端的分发,并想知道他是否考虑过其他选择,如整合DMD前端与LDC后端. Walter说,人们写信告诉他,他们喜欢使用DMD,因为它体积小,速度快.多年来,就要求他实现ARM后端. 有的人想写一个,但后来因为太难或太耗…...

编程日记 2025/7/12 23:43:33

提升网站流量的关键：AI在SEO关键词优化中的应用

内容概要在当今数字时代，提升网站流量已成为每个网站管理员的首要任务。而人工智能的技术进步，为搜索引擎优化（SEO）提供了强有力的支持，尤其是在关键词优化方面。关键词是连接用户需求与网站内容的桥梁，其…...

编程日记 2025/7/12 19:02:15

【模型对比】ChatGPT vs Kimi vs 文心一言那个更好用？数据详细解析，找出最适合你的AI辅助工具！

在这个人工智能迅猛发展的时代，AI聊天助手已经深入我们的工作与生活。你是否曾在选择使用ChatGPT、Kimi或是百度的文心一言时感到一头雾水？每款AI都有其独特的魅力与优势，那么，究竟哪一款AI聊天助手最适合你呢？本文将带…...

编程日记 2025/7/12 20:11:22

利润表在Zebra BI 中的应用（一）

效果如图。本案例采用极简式对比需要注意的是：如原始数据是一维的，则需要确保比较的各年份所含项目一致，缺失的也要占位，否则会出错！ 2022% of Revenue（占收入%） DIVIDE( [值_2022], CALCULA…...

编程日记 2025/7/8 20:07:24

12.09 C++作业2

利用函数重载，实现对整形数组的冒泡排序，对浮点型数组的冒泡排序 #include <iostream>using namespace std;int maopao(int(&ra)[10]) {//求数组长度int len sizeof(ra)/sizeof(ra[0]);int i,j,t;for(int i0;i<len;i){cin >>ra[i];}…...

编程日记 2025/7/12 23:58:07

MongoDB性能监控工具

mongostat mongostat是MongoDB自带的监控工具，其可以提供数据库节点或者整个集群当前的状态视图。该功能的设计非常类似于Linux系统中的vmstat命令，可以呈现出实时的状态变化。不同的是，mongostat所监视的对象是数据库进程。mongostat常用于…...

编程日记 2025/7/10 4:52:20

如何防范顶级应用程序安全威胁

如今的网络攻击数量是五年前的两倍多。因此，掌握最新的应用程序安全威胁对于防止数据泄露、经济损失和声誉受损至关重要。您还需要实施强大的安全实践，以保护应用程序免受最常见和最危险的威胁。顶级应用程序安全威胁......以及如何防范这些威胁 1. 注…...

编程日记 2025/7/12 2:19:29

Java版-图论-拓扑排序与有向无环图

拓扑排序拓扑排序说明对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列…...

编程日记 2025/7/8 4:04:58

汽车一键启动开关、一键启动按键、一键启动按钮

‌汽车一键启动按钮是智能汽车的重要部分，通常用于启动和关闭引擎‌。 ‌具体功能‌： ‌启动引擎‌：在许多现代汽车中，一键启动按键取代了传统的钥匙启动方式。只需轻轻按下一键启动按钮，车辆电源即被接通&#xff0c…...

编程日记 2025/7/1 7:37:57

SWIRL：有望成为2025年顶级AI搜索引擎

现在几乎每家公司都会有内部文档系统，如阿里的语雀、钉钉，字节的飞书，Confluence，印象笔记等等都可以提供给B端在局域网部署。因此，如果能把搜索功能做得高效，就能提高自家产品的竞争力。想象一下&#xf…...

编程日记 2025/7/9 16:33:59

QT requested database does not belong to the calling thread.线程中查询数据报错

QT requested database does not belong to the calling thread.线程中查询数据报错 QString name "ttx"; QSqlQueryModel* sql_model; QString sql_comm QString("select * from dssb_moddve_loddt_tab where name%1").arg(name); sql_model->set…...

编程日记 2025/7/7 2:38:10

活着就好20241210

亲爱的朋友们，大家早上好！🌞 今天是10号，星期二，2024年12月的第十天，同时也是第50周的开始，农历甲辰[龙]年十一月初六日。在这晨光熹微的美好时刻，愿那温暖而明媚的阳光轻轻拂过你的…...

编程日记 2025/7/8 1:20:46

Flutter动画（二）内建隐式动画Widget

动画效果介绍中给出了选择动画的决策树： 使用动画框架不在我们讨论的话题内。flutter支持的动画包括隐式动画和显式动画。隐式动画和显式动画隐式动画和显示动画是两种不同的动画实现方式，它们的主要区别在于控制权和动画的重复性。隐式动画&#…...

编程日记 2025/7/9 1:06:33

【人工智能基础08】卷积神经网络习题：卷积神经网络计算、图像填充、卷积的表达与设计

文章目录 1. 卷积核计算2. 卷积神经网络计算3. 卷积核关注的特征问题解答水平边缘检测与水平条纹检测45度条纹检测 4. 图像检测5. 卷积网络是特殊的全连接网络6. 输出矩阵的三种填充方法7. 卷积设计8.9 成像公式10. 卷积的计算次数11. 全连接层的计算 1. 卷积核计算卷积操作过…...

编程日记 2025/7/7 7:51:59

前端-使用vue-cli脚手架创建项目

1.下载node：2.下载完检查是否安装成功在cmd中输入：node --version或node -v 再在cmd中输入: npm -v npm默认的仓库地址是在国外，速度慢，所以设置淘宝镜像，速度就提升了，不设淘宝镜像也可以。 3.设置…...

编程日记 2025/7/8 1:18:19

功能篇：JAVA实现自定义注解

在Java中创建自定义注解可以通过使用interface关键字来完成。自定义注解可以包含元素（即参数），并且你可以指定这些元素的默认值、保留策略以及应用的目标。以下是实现自定义注解的基本步骤和示例代码。 ### 自定义注解的组成部分 1. **元素…...

编程日记 2025/7/9 22:22:28

调度系统：Temporal 在大数据领域的局限分析

在大数据领域的任务管理中，Temporal 和 Apache Airflow 各有优劣。要选择更适合的工具，需根据具体需求（如任务复杂性、依赖管理、分布式能力等）权衡。以下是两者的比较及 Temporal 在大数据领域的局限分析： Tempora…...

编程日记 2025/7/10 15:05:19

保姆级教学 uniapp绘制二维码海报并保存至相册，真机正常展示图片二维码

一、获取二维码 uni.request({url: https://api.weixin.qq.com/wxa/getwxacode?access_token${getStorage("token")},responseType: "arraybuffer",method: "POST",data: {path: "/pages/index/index"},success(res) {// 转换为 Uint…...

编程日记 2025/7/12 11:53:24

不是“我应该做什么”，而是“我想做什么”

1. 识别内心的渴望首先，我们需要识别自己真正的愿望和激情所在。这可能需要一些时间和自我反思。问自己：在没有任何外界压力的情况下，我真正想做的是什么？是赚钱、生活、旅行、追星，还是其他什么？识别这些…...

编程日记 2025/7/8 15:46:20

【openwrt】openwrt-21.02 基于IP地址使用ipset实现策略路由操作说明

openwrt版本信息 DISTRIB_ID=OpenWrt DISTRIB_RELEASE=21.02-SNAPSHOT DISTRIB_REVISION=r0-6bf6af1d5 DISTRIB_TARGET=mediatek/mt7981 DISTRIB_ARCH=aarch64_cortex-a53 DISTRIB_DESCRIPTION=OpenWrt 21.02-SNAPSHOT r0-6bf6af1d5 DISTRIB_TAINTS=no-all busybox override …...

编程日记 2025/7/9 22:11:14

地下城游戏

相关文章：