详解LeetCode地下城游戏(动态规划)——区分两种状态表示形式
地下城游戏
题目链接: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)位置时,所需的最小初始健康值。但是…...

.NET正则表达式
正则表达式提供了功能强大、灵活而又高效的方法来处理文本。 正则表达式丰富的泛模式匹配表示法使你可以快速分析大量文本,以便: 查找特定字符模式。 验证文本以确保它匹配预定义模式(如电子邮件地址)。 提取、编辑、替换或删除…...

k8s 为什么需要Pod?
Pod,是 Kubernetes 项目中最小的 API 对象,更加专业的说,Pod,是 Kubernetes 项目的原子调度单位。 Pod 是 Kubernetes 里的原子调度单位。这就意味着,Kubernetes 项目的调度器,是统一按照 Pod 而非容器的资…...

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

LDR6500:音频双C支持,数字与模拟的完美结合
在当今数字化快速发展的时代,音频设备的兼容性和性能成为了用户关注的重点。LDR6500,作为乐得瑞科技精心研发的USB Power Delivery(PD)协议芯片,凭借其卓越的性能和广泛的应用兼容性,为音频设备领域带来了新…...

python web app开发
背景: web app VS 本地GUI开发 web app开发以来一直被人诟病性能,无法访问本地设备,无状态的等缺点而被迫转向本地GUI开发;但本地开发如C++ QT,MFC,WinForm等开发结构又太重,使人望而生畏。web app有个有点就…...

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

【unity小技巧】分享vscode如何进行unity开发,且如何开启unity断点调试模式,并进行unity断点调试(2024年最新的方法,实测有效)
文章目录 前言一、前置条件1、已安装Visual Studio Code,并且unity首选项>外部工具>外部脚本编辑器选择为Visual Studio Code [版本号],2、在Visual Studio Code扩展中搜索Unity,并安装3、同时注意这个插件下面的描述,需要根…...

AI大模型学习笔记|人工智能的发展历程、智能体的发展、机器学习与深度学习的基本理论
学习链接:冒死上传!价值2W的大模型入门到就业教程分享给大家!轻松打造专属大模型助手,—多模态、Agent、LangChain、ViT、NLP_哔哩哔哩_bilibili 百度网盘自己整理的笔记: 通过网盘分享的文件:1-人工智能的…...

C#实现一个HttpClient集成通义千问-多轮对话功能实现
多轮对话功能实现 视频教程实现原理消息的类型 功能开发消息类修改请求体修改发送请求函数修改用户消息输入 多轮对话的token消息完整文档消息类型 视频教程 .NetAI开发入门HttpClient实现通义千问集成-多轮对话功能实现 实现原理 一直保留更新messages 现在设置的meessages只…...

Java Web 7 请求响应(Postman)
前言(SpringBoot程序请求响应流程) 以上一章的程序为例,一个基于SpringBoot的方式开发一个web应用,浏览器发起请求 /hello 后 ,给浏览器返回字符串 “Hello World ~”。 而我们在开发web程序时呢,定义了一…...

Android APP自学笔记
摘抄于大学期间记录在QQ空间的一篇自学笔记,当前清理空间,本来想直接删除掉的,但是感觉有些舍不得,因此先搬移过来。 Android导入已有外部数据库 2015.06.26在QQ空间记录:在Android中不能直接打开res aw目录中的数据…...

Linux 系统报打开的文件过多
1.问题 1804012290 [reactor-http-epoll-1] WARN i.n.channel.DefaultChannelPipeline - An exceptionCaught() event was fired, and it reached at the tail of the pipeline. It usually means the last handler in the pipeline did not handle the exception. - io.nett…...

javaWeb之过滤器(Filter)
目录 前言 过滤器概述 什么是过滤器 过滤器详细 过滤器的生命周期 过滤器的应用 创建一个简单的Filter类步骤 注意:指定拦截路径,我们有两种方式 实例 前言 本篇博客的核心 知道过滤器的整个拦截过程知道如何指定拦截路径知道过滤器的生命周期…...

ModStartBlog v10.0.0 发布时间自定义,多图快速粘贴,博客编辑器升级
ModStart 是一个基于 Laravel 模块化极速开发框架。模块市场拥有丰富的功能应用,支持后台一键快速安装,让开发者能快的实现业务功能开发。 系统完全开源,基于 Apache 2.0 开源协议。 功能特性 丰富的模块市场,后台一键快速安装 …...

Unexpected token ‘<‘, “<!doctype “... is not valid JSON
Unexpected token ‘<’, "<!doctype "… is not valid JSON 在前端开发时,遇到以下报错内容。 1.报错内容如下: // 报错内容 Uncaught (in promise) SyntaxError: Unexpected token <, "<!doctype "... is not valid…...

24/12/9 算法笔记<强化学习> PPO,DPPO
PPO是目前非常流行的增强学习算法,OpenAI把PPO作为目前baseline算法,首选PPO,可想而知,PPO可能不是最强的,但是是最广泛的。 PPO是基于AC架构,因为AC架构有一个好处,就是解决了连续动作空间的问…...

Linux下编译安装METIS
本文记录Linux下编译安装METIS的流程。 零、环境 操作系统Ubuntu 22.04.4 LTSVS Code1.92.1Git2.34.1GCC11.4.0CMake3.22.1 一、安装依赖 1.1 下载GKlib sudo apt-get install build-essential sudo apt-get install cmake 2.2 编译安装GKlib 下载GKlib代码, …...

【数据库】关系代数和SQL语句
一 对于教学数据库的三个基本表 学生S(S#,SNAME,AGE,SEX) 学习SC(S#,C#,GRADE) 课程(C#,CNAME,TEACHER) (1)试用关系代数表达式和SQL语句表示:检索WANG同学不学的课程号 select C# from C where C# not in(select C# from SCwhere S# in…...

amazon亚马逊滑动识别验证码
注意,本文只提供学习的思路,严禁违反法律以及破坏信息系统等行为,本文只提供思路 如有侵犯,请联系作者下架 本文识别已同步上线至OCR识别网站: http://yxlocr.nat300.top/ocr/other/15 亚马逊的滑动还原验证码数据集如下: 和某顶象的差不多,图片分割高度是中间固定的,…...

Android Studio 创建虚拟设备的详细图文操作教程
本篇文章主要讲解 Android Studio 创建模拟器详细图文操作,包含了每一步的详细操作,便于理解和掌握对模拟的创建。 日期:2024年12月9日 作者:任聪聪 运行效果: 说明:创建运行后,点击右侧如下图…...

网络安全法-附则
第七章 附 则 第七十六条 本法下列用语的含义: (一)网络,是指由计算机或者其他信息终端及相关设备组成的按照一定的规则和程序对信息进行收集、存储、传输、交换、处理的系统。 (二)网络安全ÿ…...

CSS核心(上)
CSS 介绍 层叠样式表(英语:Cascading Style Sheets, 缩写:CSS; 又叫串样式列表,级联样式表,串接样式表,阶层式样式表)是一种用来为结构化文档(HTML或XML应用)添加样式(…...

深度学习常用损失函数介绍
均方差损失(Mean Square Error,MSE) 均方误差损失又称为二次损失、L2损失,常用于回归预测任务中。均方误差函数通过计算预测值和实际值之间距离(即误差)的平方来衡量模型优劣。即预测值和真实值越接近&…...

HarmonyOS-中级(四)
文章目录 Native适配开发三方库的基本使用 🏡作者主页:点击! 🤖HarmonyOS专栏:点击! ⏰️创作时间:2024年12月09日11点12分 Native适配开发 Node-API HarmonyOS Node-API 是 HarmonyOS 提供的…...

React v19稳定版发布12.5
🤖 作者简介:水煮白菜王 ,一位资深前端劝退师 👻 👀 文章专栏: 前端专栏 ,记录一下平时在博客写作中,总结出的一些开发技巧✍。 感谢支持💕💕💕 目…...

【毕业设计选题】深度学习类毕业设计选题参考 开题指导
目录 前言 毕设选题 开题指导建议 更多精选选题 选题帮助 最后 前言 大家好,这里是海浪学长毕设专题! 大四是整个大学期间最忙碌的时光,一边要忙着准备考研、考公、考教资或者实习为毕业后面临的升学就业做准备,一边要为毕业设计耗费大量精力。学长给大家整…...

NanoLog起步笔记-4-Server端的两个线程
nonolog起步笔记-4-Server端的两个线程 Server端的两个线程两个线程的角色与各自的职责RuntimeLogger::compressionThreadMain线程 详细学习一下相关的代码第三个线程第一次出现原位置swip buffer Server端的两个线程 如前所述,nanolog的server端,相对而…...

linux zookeeper安装并服务化
1.版本信息 系统:centos7.6 java版本:java 8(已经安装好) zookeeper版本:3.6.3 2.zookeeper安装并测试 1.上传文件至指定目录并解压 切换至cd downloads 目录下, rz上传文件 解压:tar -zxvf apache-zookeeper-3.…...

很简单,但是很实用。把docker run改写成docker compose。
很简单,但是很实用。把docker run改写成docker compose。 在Docker的世界里,docker run命令是启动容器最直接的方式之一。然而,当项目复杂度增加,涉及多个服务时,管理这些容器和服务之间的依赖关系就会变得繁琐。这时,使用Docker Compose来定义和运行多容器Docker应用就…...