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

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 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里&#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻…...

Linux定时任务crontab

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

golang字符串切片去重

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

git如何检查和修改忽略文件和忽略规则

查询忽略规则 使用命令行&#xff1a;git status --ignored&#xff0c;进行查询&#xff0c; 例&#xff1a; $ 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 &#xff0c;是带标题栏的。 记录下 修改标题栏名称 和 隐藏标题栏 的方法。 修改标题栏名称 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&#xff1a;https://github.com/conda/conda/issues/7980...

FreeMarker--表达式和运算符的用法(全面/有示例)

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

设计模式 -- 策略模式(传统面向对象与JavaScript 的对比实现)

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

非常详细的 Ceph 介绍、原理、架构

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

js 的正则表达式(二)

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

星际争霸之小霸王之小蜜蜂(四)--事件监听-让小蜜蜂动起来

目录 前言 一、监听按键并作出判断 二、持续移动 三、左右移动 总结&#xff1a; 前言 今天开始正式操控我们的小蜜蜂了&#xff0c;之前学java的时候是有一个函数监听鼠标和键盘的操作&#xff0c;我们通过传过来不同的值进行判断&#xff0c;现在来看看python是否一样的实现…...

Visual Studio 2022 你必须知道的实用调试技巧

目录 1、什么是bug&#xff1f; 2.调试是什么&#xff1f;有多重要&#xff1f; 2.1我们是如何写代码的&#xff1f; 2.2又是如何排查出现的问题的呢&#xff1f; ​编辑 2.3 调试是什么&#xff1f; 2.4调试的基本步骤 2.5Debug和Release的介绍 3.Windows环境调试介绍…...

Webgl 存储限定符attribute、gl.getAttribLocation、gl.vertexAttrib3f及其同族函数和矢量版本的介绍

目录 attribute变量规范 获取attribute变量的存储位置 gl.getAttribLocation&#xff08;&#xff09;函数的规范&#xff1a; 向attribute变量赋值 gl.vertexAttrib3f&#xff08;&#xff09;的规范。 gl.vertexAttrib3f&#xff08;&#xff09;的同族函数 示例代码…...

postgresql跨库创建视图

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

FPGA时钟

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

FifthOne:计算机视觉提示和技巧

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

Oracle19c-补丁升级报错合集(一)

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

嵌入式:ARM Day6

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

ClickHouse安装步骤

文章目录 ClickHouse安装步骤背景安装启动用户相关修改密码登录验证新增用户config配置文件 基本操作服务管理 ClickHouse安装步骤 背景 经过研究ClickHouse是列式数据库&#xff0c;下面是在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循环&#xff1a;可以类比C语言中的while循环进行学习&#xff0c;详见本人原创博客链接&#xff1a; https://blog.csdn.net/qq_41878292/article/details/132081302?spm1001.2014.3001.5502伪代码表示&#xff1a; while 表达式 do循环体 done用法类比S…...

【校招VIP】CSS校招考点之选择器优先级

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

Netty+springboot开发即时通讯系统笔记(四)终

实时性 1.线程池多线程&#xff0c;把消息同步给其他端和对方用户&#xff0c;其中数据持久化往往是最浪费时间的操作&#xff0c;可以使用mq异步存储&#xff0c;因为其他业务不需要拿着整条数据&#xff0c;只需要这条数据的id进行操作。 2。消息校验前置&#xff0c;放在t…...

java -jar 启动服务后,关闭命令窗口后服务停止

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

Android PowerManager的使用

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

安防监控/视频集中存储/云存储平台EasyCVR v3.3增加首页告警类型

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

7-6 统计字符出现次数

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

美国大模型风向速报(一)为何重视提示工程?LangChain+向量数据库+开源大模型真香...

多家&#xff0c;且独家来自美国的信源同时向“亲爱的数据”表示&#xff0c; 提示工程&#xff08;Prompt Engineering&#xff09;在美国大模型领域备受重视。 读者都要聊&#xff0c; 那就干活。 &#xff08;一&#xff09;开源真香 现阶段&#xff0c;AI开源极客大展身手&…...

excel统计函数篇2之count系列

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

vue3组件多个根节点报错

打开扩展商店搜索下载 vetur 打开设置命令面板 搜索eslint 将下面的勾选取消...