174.地下城游戏——LeetCode
题目
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出:7
解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。
解题思路
这个问题是一个典型的动态规划问题,我们需要找到从左上角到右下角的路径上,骑士所需的最小初始健康点数,使得在任何时候骑士的健康点数都不会降到0或以下。
动态规划的状态转移方程应该是这样的:
设 dp[i][j] 表示到达房间 (i, j) 时所需的最小生命值。由于骑士可以选择向下或向右移动,dp[i][j] 可以通过 dp[i+1][j](从上方房间来)或 dp[i][j+1](从左侧房间来)计算得出。我们需要考虑以下两种情况:
- 如果从上方房间
(i+1, j)来,骑士需要在当前房间(i, j)至少剩余dp[i+1][j] - dungeon[i+1][j]生命值。 - 如果从左侧房间
(i, j+1)来,骑士需要在当前房间(i, j)至少剩余dp[i][j+1] - dungeon[i][j+1]生命值。
我们需要取这两种情况中的较大者,因为骑士需要在进入房间前保证足够的生命值。然后,我们需要考虑当前房间 (i, j) 的效果 dungeon[i][j],如果 dungeon[i][j] 是负数,骑士将失去生命值。
因此,状态转移方程为:
解题过程
-
初始化
dp数组,其大小与dungeon相同。 -
设置右下角的
dp值,根据房间值决定初始健康点数。 -
从右下角开始向上和向左遍历
dungeon,填充dp数组。 -
对于每个格子
(i, j),计算从右边(i, j+1)和下面(i+1, j)到达的最小健康点数,并取较小者。 -
从计算结果中减去当前格子的值,确保结果至少为1(因为骑士不能有0或负的健康点数)。
-
循环结束后,
dp[0][0]就是所需的最小初始健康点数。
复杂度
-
时间复杂度:O(m×n)O(m×n),其中
m和n分别是dungeon的行数和列数。我们需要遍历整个dungeon。 -
空间复杂度:O(m×n)O(m×n),用于存储动态规划表
dp。如果只存储一行或一列的状态,可以优化到 O(min(m,n))O(min(m,n))。
Code
class Solution {public int calculateMinimumHP(int[][] dungeon) {final int m = dungeon.length, n = dungeon[0].length;int[][] dp = new int[m][n];// 初始化dp数组的右下角dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);// 从右下角开始向上和向左遍历for (int i = m - 2; i >= 0; i--) {dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);}for (int j = n - 2; j >= 0; j--) {dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);}// 动态规划填表for (int i = m - 2; i >= 0; i--) {for (int j = n - 2; j >= 0; j--) {// 取右边和下边的最小值,并减去当前房间的值dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);}}return dp[0][0];}
}相关文章:
174.地下城游戏——LeetCode
题目 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻…...
登录相关功能的优化【JWT令牌+拦截器+跨域】
登录相关功能的优化 登录后显示当前登录用户el-dropdown: Element - The worlds most popular Vue UI framework <el-dropdown style"float: right; height: 60px; line-height: 60px"><span class"el-dropdown-link" style"color: white;…...
向日葵没有显示器会卡住
前言 有一台机器【ubuntu20】,用于远程开发,使用向日葵时候,如果不接显示器是会卡住的。。。 显示屏是有限的,所以现在解决一下这个问题。 卡在登录界面 双击启动 由于Ubuntu默认显示管理器是gdm,而向日葵使用的是l…...
【机器学习西瓜书学习笔记——聚类】
机器学习西瓜书学习笔记【第九章】 第九章 聚类9.1 聚类任务9.2 性能度量两类指标 9.3距离计算基本性质属性有序属性无序属性 混合距离加权距离 9.4 原型聚类K-MEANS聚类算法步骤优势劣势 学习向量量化高斯混合聚类步骤难点例子EM思想的体现小结 9.5 密度聚类9.6 层次聚类 第九…...
MATLAB(8)深度变化模型
一、前言 在MATLAB中模拟深度变化模型通常依赖于具体的应用场景,比如海洋深度、地下水深度、地形高度变化等。由于“深度变化”可以涉及多种物理过程和数学模型,我将提供一个简化的示例,该示例模拟了一个基于时间变化的深度变化模型ÿ…...
mp3格式转换器哪个好用?汇总七款音频格式转换方法(无损转换)
音乐已经成为我们生活中不可或缺的一部分。但是在播放的时候,可能会遇到音频格式不兼容的情况。特别是在一些下载站或音乐平台获取的音频,有些特殊格式在播放器上无法正常播放,一般这种情况我们需要借助mp3转换器解决。 mp3是一种常见的数字音…...
移行前的复盘:CodeCommit 的重要地位分析
前言 截至7月28日,关于AWS CodeCommit的现状如下: 现有账号的现有存储库可以继续使用CodeCommit,不受限制。之前未使用过CodeCommit的账号(或没有现有存储库的账号)无法创建新的存储库。 这并不意味着CodeCommit的服…...
Java中等题-括号生成(力扣)
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((()))","(()())","(())()","()(())","()()(…...
Flink 实时数仓(八)【DWS 层搭建(二)流量域、用户域、交易域搭建】
前言 今天的任务是完成流量域最后一个需求、用户域的两个需求以及交易域的部分需求; 1、流量域页面浏览各窗口汇总表 任务:从 Kafka 页面日志主题读取数据,统计当日的首页和商品详情页独立访客数。 注意:一般我们谈到访客&…...
gitlab-runner /var/run/docker.sock connect permission denied
usermod -aG docker gitlab-runner sudo service docker restart参考:https://gitlab.com/gitlab-org/gitlab-runner/-/issues/3492...
网络安全 - 应急响应检查表
前言 本项目旨在为应急响应提供全方位辅助,以便快速解决问题。结合自身经验和网络资料,形成检查清单,期待大家提供更多技巧,共同完善本项目。愿大家在应急之路一帆风顺。 图片皆来源于网络,如有侵权请联系删除。 一…...
AD常用PCB设计规则介绍 (详细版)
AD09常用PCB设计规则介绍 电气设计规则用来设置在电路板布线过程中所遵循的电气方面的规则,包括安全间距、短路、未布线网络和未连接引脚这四个方面的规则: (1)、安全间距规则(clearance) 该规则用于设定在PCB设计中࿰…...
mysql主从服务配置
主从MySQL服务器 [rootlocalhost ~]# yum -y install ntpdate [rootlocalhost ~]# ntpdate cn.ntp.org.cn [rootlocalhost ~]# yum -y install rsync [rootlocalhost ~]# vim mysql.sh #!/bin/bash yum list installed |grep libaio if [ $? ne 0 ]; then yum -y install…...
Redis基础总结、持久化、主从复制、哨兵模式、内存淘汰策略、缓存
文章目录 Redis 基础Redis 是什么,有哪些特点为什么要使用 Redis 而不仅仅依赖 MySQLRedis 是单线程吗Redis 单线程为什么还这么快 Redis 数据类型和数据结构五种基本数据结构及应用场景其他数据类型Redis 底层数据结构 Redis 持久化数据不丢失的实现AOF 日志RDB 快…...
Java与Python优劣势对比:具体例子与深入分析
在软件开发的世界里,Java和Python是两座不可忽视的高峰。它们各自拥有独特的优势和应用场景,为开发者提供了多样化的选择。本文将通过具体例子,深入分析Java和Python在不同方面的表现,以期为读者提供更为详尽的参考。 1. 语法简洁…...
C++内存泄漏介绍
C内存泄漏(Memory Leak)是指程序在运行过程中,动态分配的内存没有被适当地释放或回收,导致这部分内存始终被占用,无法再被程序或其他程序使用。这种情况通常发生在使用了new或malloc等函数动态分配内存后,忘…...
C++分析红黑树
目录 红黑树介绍 红黑树的性质与平衡控制关系 红黑树节点的插入 情况1:不需要调整 情况2:uncle节点为红色 情况3:uncle节点为黑色 总结与代码实现 红黑树的删除(待实现) 红黑树的效率 红黑树介绍 红黑树是第二种平衡二…...
mysql线上查询之前要性能调优
查询优化是数据库性能调优的关键方面,目的是减少查询的执行时间和资源消耗。以下是一些常见的查询优化技巧及其示例: 使用合适的索引 问题: 全表扫描导致查询缓慢优化: 为经常用于搜索条件的列添加索引示例: 假设有一…...
GPIO输出控制之LED闪烁、LED流水灯以及蜂鸣器应用案例
系列文章目录 STM32之GPIO(General Purpose Input/Output,通用型输入输出) 文章目录 系列文章目录前言一、LED和蜂鸣器简介1.1 LED1.2 蜂鸣器1.3 面包板 二、LED硬件电路2.1 低电平驱动电路2.2 高电平驱动电路 三、蜂鸣器硬件电路3.1 PNP型三…...
体系结构论文导读(三十四):Design of Reliable DNN Accelerator with Un-reliable ReRAM
文章核心 这篇文章主要讨论了一种在不可靠的ReRAM(阻变存储器)设备上设计可靠的深度神经网络(DNN)加速器的方法。文章提出了两种关键技术来解决ReRAM固有的不可靠性问题:动态定点(DFP)数据表示…...
Phi-4-reasoning-vision-15B基础教程:图像上传→提问→模式选择→结果解读
Phi-4-reasoning-vision-15B基础教程:图像上传→提问→模式选择→结果解读 1. 快速认识Phi-4-reasoning-vision-15B Phi-4-reasoning-vision-15B是一款强大的视觉多模态推理模型,它能像人类一样"看"图片并回答相关问题。想象一下,…...
网络安全视角下的Qwen3-ForcedAligner服务防护策略
网络安全视角下的Qwen3-ForcedAligner服务防护策略 1. 语音对齐服务面临的真实安全挑战 在企业级AI语音处理系统中,Qwen3-ForcedAligner作为关键的语音强制对齐组件,承担着将语音与文本精确匹配、生成时间戳的核心任务。当它被部署为对外提供API服务时…...
Overleaf上LaTeX Beamer字体自定义实战:手把手教你用fontspec包搞定中文和英文字体
Overleaf平台LaTeX Beamer字体定制全攻略:从基础配置到高级技巧 在学术报告和教学演示领域,LaTeX Beamer因其专业的排版质量和稳定的输出效果而备受青睐。然而,当涉及到中英混排场景时,许多用户都会遇到字体配置的挑战——如何让中…...
Ozon运营5大核心场景,Captain AI全功能精准赋能
做Ozon运营,不少卖家会遇到这样的场景:选品时纠结不定,不清楚哪类产品适配市场、合规且有盈利空间;新品上架后缺乏有效推广思路,流量难以提升;财税申报流程复杂,担心操作失误引发违规;物流方案选择困难,难以平衡成本与时效;对账时面对俄语账单无从下手,无法清晰掌握…...
ZTE ONU工厂模式解锁:3个关键步骤告别运维困境
ZTE ONU工厂模式解锁:3个关键步骤告别运维困境 【免费下载链接】zteOnu A tool that can open ZTE onu device factory mode 项目地址: https://gitcode.com/gh_mirrors/zt/zteOnu zteOnu是一款专为网络运维工程师设计的专业工具,能够快速解锁ZTE…...
【Unity中固定宽度文本截断与省略号处理方案】
在UI设计中经常遇到文本内容超出固定宽度的情况,需要实现自动截断并添加省略号的效果。以下是几种实用解决方案:一:Text组件的自动处理Unity的Text组件自带水平溢出处理功能:在Inspector面板找到Text组件设置Horizontal Overflow为…...
Pixel Aurora Engine 与MySQL联动:构建带审核的图像素材管理库
Pixel Aurora Engine与MySQL联动:构建带审核的图像素材管理库 1. 业务场景与痛点分析 电商设计团队每天需要制作大量商品展示图,传统设计流程面临三大挑战: 人力成本高:每张主图需要设计师2-3小时制作风格不统一:不…...
虚拟机热迁移实战指南:从核心原理到生产环境部署与调优
1. 虚拟机热迁移的核心原理 第一次接触热迁移时,我被这个技术的神奇之处震撼到了——就像给飞行中的飞机更换引擎,乘客完全感受不到任何颠簸。虚拟机热迁移(Live Migration)的本质,就是在不中断服务的情况下ÿ…...
2026奇点智能技术大会核心技术解密(AI原生研发全链路SOP首次公开)
第一章:2026奇点智能技术大会:AI原生研发全流程拆解 2026奇点智能技术大会(https://ml-summit.org) 在2026奇点智能技术大会上,AI原生研发不再停留于模型微调与API调用,而是贯穿从需求建模、数据契约定义、可验证推理生成&#x…...
如何通过手机号快速找回QQ号:开源工具的3分钟解决方案
如何通过手机号快速找回QQ号:开源工具的3分钟解决方案 【免费下载链接】phone2qq 项目地址: https://gitcode.com/gh_mirrors/ph/phone2qq 在数字生活中,你是否曾因忘记QQ账号而焦急万分?手机更换、系统重装或长期未登录,…...
