174-地下城游戏
题目
恶魔们抓住了公主并将她关在了地下城 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
思路
问题描述:地下城由一个m x n的网格组成,骑士从左上角出发,必须通过对抗恶魔来拯救公主,目标是找到骑士进入地下城所需的最低初始健康点数。
解题思路:
这是一个动态规划问题。我们可以从右下角开始逆向考虑,定义 dp[i][j]
为从位置 (i, j)
到达右下角时所需的最低初始健康点数。为了逆向推导,我们从右下角开始向左上角遍历。
- 对于最后一行和最后一列,只能往右或往下移动,因此需要考虑从当前位置
(i, j)
出发的下一个位置(i+1, j)
或(i, j+1)
,并且需要保证dp[i][j]
大于等于1。 - 对于其他位置,我们需要考虑向右或向下移动,并且选择路径中的最小初始健康点数。因此,
dp[i][j]
取决于(i+1, j)
和(i, j+1)
中的较小值,且需要保证dp[i][j]
大于等于1。
最终,初始健康点数应该大于等于 dp[0][0]
。
代码
object Solution {def calculateMinimumHP(dungeon: Array[Array[Int]]): Int = {val m = dungeon.lengthval n = dungeon(0).lengthval dp = Array.ofDim[Int](m, n)dp(m - 1)(n - 1) = math.max(1, 1 - dungeon(m - 1)(n - 1))for (i <- m - 2 to 0 by -1) {dp(i)(n - 1) = math.max(1, dp(i + 1)(n - 1) - dungeon(i)(n - 1))}for (j <- n - 2 to 0 by -1) {dp(m - 1)(j) = math.max(1, dp(m - 1)(j + 1) - dungeon(m - 1)(j))}for (i <- m - 2 to 0 by -1) {for (j <- n - 2 to 0 by -1) {dp(i)(j) = math.max(1, math.min(dp(i + 1)(j), dp(i)(j + 1)) - dungeon(i)(j))}}dp(0)(0)}def main(args: Array[String]): Unit = {val dungeon1 = Array(Array(-2, -3, 3), Array(-5, -10, 1), Array(10, 30, -5))println(calculateMinimumHP(dungeon1)) // 输出 7val dungeon2 = Array(Array(0))println(calculateMinimumHP(dungeon2)) // 输出 1}
}
相关文章:

174-地下城游戏
题目 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻…...

Linux定时任务crontab
常用命令 crontab -e 进入定时脚本,编辑后保存即立即生效 crontab -l 查看用户定时脚本 tail -f /var/log/cron 查看执行日志 service crond status 查看定时器运行状态 service crond restart 重启定时器 定时任务不执行原因 定时任务设置的格式正确,手…...

golang字符串切片去重
函数的功能是从输入的字符串切片中去除重复的元素,并返回去重后的结果。具体的实现逻辑如下: 创建一个空的结果切片result,用于存储去重后的字符串。创建一个临时的maptempMap,用于存放不重复的字符串。map的键是字符串࿰…...

git如何检查和修改忽略文件和忽略规则
查询忽略规则 使用命令行:git status --ignored,进行查询, 例: $ git status --ignored On branch develop Your branch is up to date with origin/develop.Ignored files:(use "git add -f <file>..." to inc…...

Android AppCompatActivity标题栏操作
使用 AndroidStudio 新建的工程默认用 AppCompatActivity ,是带标题栏的。 记录下 修改标题栏名称 和 隐藏标题栏 的方法。 修改标题栏名称 Override protected void onCreate(Bundle savedInstanceState) {super.onCreate(savedInstanceState);setContentView(R…...

解决conda activate报错
解决方法 source ~/anaconda3/bin/activate或 source ~/miniconda3/bin/activate然后就可以使用 conda activate xxx环境了 问题解析 请参考github:https://github.com/conda/conda/issues/7980...

FreeMarker--表达式和运算符的用法(全面/有示例)
原文网址:FreeMarker--表达式和运算符的用法(全面/有示例)_IT利刃出鞘的博客-CSDN博客 简介 本文介绍FreeMarker的表达式和运算符的用法。 表达式是FreeMarker的核心功能。表达式放置在插值语法(${...})之中时,表明需要输出表达…...

设计模式 -- 策略模式(传统面向对象与JavaScript 的对比实现)
设计模式 – 策略模式(传统面向对象与JavaScript 的对比实现) 文章目录 设计模式 -- 策略模式(传统面向对象与JavaScript 的对比实现)使用策略模式计算年终奖初级实现缺点 使用组合函数重构代码缺点 使用策略模式重构代码传统的面…...

非常详细的 Ceph 介绍、原理、架构
1. Ceph架构简介及使用场景介绍 1.1 Ceph简介 Ceph是一个统一的分布式存储系统,设计初衷是提供较好的性能、可靠性和可扩展性。 Ceph项目最早起源于Sage就读博士期间的工作(最早的成果于2004年发表),并随后贡献给开源社区。在经过…...

js 的正则表达式(二)
1.正则表达式分类: 正则表达式分为普通字符和元字符。 普通字符: 仅能够描述它们本身,这些字符称作普通字符,例如所有的字母和数字。也就是说普通字符只能够匹配字符串中与它们相同的字符。 元字符: 是一些具有特殊含…...

星际争霸之小霸王之小蜜蜂(四)--事件监听-让小蜜蜂动起来
目录 前言 一、监听按键并作出判断 二、持续移动 三、左右移动 总结: 前言 今天开始正式操控我们的小蜜蜂了,之前学java的时候是有一个函数监听鼠标和键盘的操作,我们通过传过来不同的值进行判断,现在来看看python是否一样的实现…...

Visual Studio 2022 你必须知道的实用调试技巧
目录 1、什么是bug? 2.调试是什么?有多重要? 2.1我们是如何写代码的? 2.2又是如何排查出现的问题的呢? 编辑 2.3 调试是什么? 2.4调试的基本步骤 2.5Debug和Release的介绍 3.Windows环境调试介绍…...

Webgl 存储限定符attribute、gl.getAttribLocation、gl.vertexAttrib3f及其同族函数和矢量版本的介绍
目录 attribute变量规范 获取attribute变量的存储位置 gl.getAttribLocation()函数的规范: 向attribute变量赋值 gl.vertexAttrib3f()的规范。 gl.vertexAttrib3f()的同族函数 示例代码…...

postgresql跨库创建视图
需求: A库a表中的字段拆分1个到B库b表,所以b表中只保留唯一标识字段(可以理解为id)和另一个被拆分的字段 需要用到的拓展:CREATE EXTENSION dblink 使用dblink创建连接: SELECT dblink_connect(other_db, hostaddr【IP…...

FPGA时钟
几年前FPGA时钟只需要连接一个单端输入的晶振,非常容易。现在不同了,差分时钟输入,差分信号又分为LVDS和LVPECL,时钟芯片输出后还要经过直流或交流耦合才能接入FPGA,有点晕了,今天仔细研究一下。 FPGA输入…...

FifthOne:计算机视觉提示和技巧
一、说明 欢迎来到我们每周的FiftyOne提示和技巧博客,我们回顾了最近在Slack,GitHub,Stack Overflow和Reddit上弹出的问题和答案。FiftyOne是一个开源机器学习工具集,使数据科学团队能够通过帮助他们策划高质量数据集、评估模型、…...

Oracle19c-补丁升级报错合集(一)
前言: 本文主要介绍Oracle19c补丁升级遇到的问题,涉及安装补丁prepatch步骤,apply应用报错以及datapatch -verbose数据字典更新报错 问题一: 在执行补丁rootcrs.sh -prepatch操作时,发生执行检查命令cluutil -chkshare报错 CLSRSC-180: An …...

嵌入式:ARM Day6
作业:完成cortex-A7核UART总线实验 目的:1.输入a,显示b,将输入的字符的ASCII码下一位字符输出 2.原样输出输入的字符串 源码: uart4.h #ifndef __UART4_H__ #define __UART4_H__#include "stm32mp1xx_rcc.h" #incl…...

ClickHouse安装步骤
文章目录 ClickHouse安装步骤背景安装启动用户相关修改密码登录验证新增用户config配置文件 基本操作服务管理 ClickHouse安装步骤 背景 经过研究ClickHouse是列式数据库,下面是在Centos7.9版本单机版的安装的演示 安装 首先安装yum-utils工具包 sudo yum inst…...

Android CCodec (二十) CCodec Native服务实现分析
1、C2解码服务registerAsService注册流程 google实现CCodec的vendor默认解码服务代码路径是在frameworks/av/media/codec2/hidl/services/vendor.cpp中,而其注册的是HIDL服务,本文就对HIDL服务注册做简要分析。首先看下vendor.cpp中的代码注册流程。 int main(int /* argc *…...

Shell编程学习之while循环语句和for循环语句的应用
Shell编程中的while循环:可以类比C语言中的while循环进行学习,详见本人原创博客链接: https://blog.csdn.net/qq_41878292/article/details/132081302?spm1001.2014.3001.5502伪代码表示: while 表达式 do循环体 done用法类比S…...

【校招VIP】CSS校招考点之选择器优先级
考点介绍: 选择器是CSS的基础,也是校招中的高频考点,特别是复合选择器的执行优先级,同时也是实战中样式不生效的跟踪依据。 因为选择器的种类较多,很难直接记忆,可以考虑选择一个相对值,比如id类…...

Netty+springboot开发即时通讯系统笔记(四)终
实时性 1.线程池多线程,把消息同步给其他端和对方用户,其中数据持久化往往是最浪费时间的操作,可以使用mq异步存储,因为其他业务不需要拿着整条数据,只需要这条数据的id进行操作。 2。消息校验前置,放在t…...

java -jar 启动服务后,关闭命令窗口后服务停止
java -jar 启动服务后,关闭命令窗口后服务停止 问题:当我们用java -jar命令启动服务后,只有一直保持Xshell的窗口开启且正常连接服务器时才能访问服务,当关闭命令窗口时,服务会停止运行 解决:使用nohup命…...

Android PowerManager的使用
唤醒锁定 如果需要使 CPU 保持运行状态,以便在设备进入休眠模式之前完成某项工作,可以使用“唤醒锁定” 。 添加权限 <uses-permission android:name"android.permission.WAKE_LOCK" />设置唤醒锁定 PowerManager powerManager (Po…...

安防监控/视频集中存储/云存储平台EasyCVR v3.3增加首页告警类型
安防监控/视频集中存储/云存储EasyCVR视频汇聚平台,可支持海量视频的轻量化接入与汇聚管理。平台能提供视频存储磁盘阵列、视频监控直播、视频轮播、视频录像、云存储、回放与检索、智能告警、服务器集群、语音对讲、云台控制、电子地图、平台级联、H.265自动转码等…...

7-6 统计字符出现次数
分数 20 全屏浏览题目 切换布局 作者 C课程组 单位 浙江大学 本题要求编写程序,统计并输出某给定字符在给定字符串中出现的次数。 输入格式: 输入第一行给出一个以回车结束的字符串(少于80个字符);第二行输入一个…...

美国大模型风向速报(一)为何重视提示工程?LangChain+向量数据库+开源大模型真香...
多家,且独家来自美国的信源同时向“亲爱的数据”表示, 提示工程(Prompt Engineering)在美国大模型领域备受重视。 读者都要聊, 那就干活。 (一)开源真香 现阶段,AI开源极客大展身手&…...

excel统计函数篇2之count系列
1、COUNT(value1,[value2],…):计算参数列表中数字的个数 2、COUNTA(value1,[value2],…):计算参数列表中值的个数 联想在excel之数学函数、excel中的通配符一文中提到求和函数: SUMIF(range,ceriteria,[sum_range]):对范围内符合指定条件的…...

vue3组件多个根节点报错
打开扩展商店搜索下载 vetur 打开设置命令面板 搜索eslint 将下面的勾选取消...