leetcode做题笔记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

思路一:动态规划

c++解法

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(),n = dungeon[0].size();vector<vector<int>> dp(m,vector<int>(n,0));dp[m-1][n-1] = dungeon[m-1][n-1];for(int i = m-2;i>=0;i--){dp[i][n-1] = min(dungeon[i][n-1],(dp[i+1][n-1]+dungeon[i][n-1]));}for(int j = n-2;j>=0;j--){dp[m-1][j] = min(dungeon[m-1][j],(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] = min(dungeon[i][j],max(dp[i+1][j],dp[i][j+1])+dungeon[i][j]);}}return dp[0][0]>0?1:-1*dp[0][0]+1;}
};

分析:

本题要计算到达右下角的最少起始点数,可以利用动态规划的方法每向右或向左走一步则比较右边和下边哪个更小,动态规划则将下一步比较新步的初始步和右下三种情况的最小值来计算dp[i][j]值,最后返回dp[0][0],并判断是否大于零,若大于则返回1;

总结:

本题考察动态规划的应用,找到状态方程后可解决,时间复杂度为O(n^2),空间复杂度为O(n^2)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/160716.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java应用性能问题诊断技巧

作者&#xff1a;张彦东 参考&#xff1a;https://developer.aliyun.com/ebook/450?spma2c6h.20345107.ebook-index.28.6eb21f54J7SUYc 文章目录 &#xff08;一&#xff09;内存1.内存2.内存-JMX3.内存-Jmap4.内存-结合代码确认问题 &#xff08;二&#xff09;CPU1.CPU-JMX或…

史上最短的“牛熊转换”:BTC价格昨夜起飞,但却来自一条假新闻!

昨夜&#xff0c;加密市场经历了史上最短的一次“牛熊转换”。 在短短10分钟内&#xff0c;BTC快速走出多根阳线&#xff0c;价格直接起飞&#xff0c;连续突破28000美元、29000美元、30000美元的整数关口&#xff0c;最高触及30535.8美元&#xff0c;涨幅近10%&#xff08;数据…

Compose Canvas基础(2) 图形转换

Compose Canvas基础&#xff08;2&#xff09;图形转换 前言平移 translate缩放 scale旋转 rotate自定义绘图区域及绘制内边距inset组合转换 withTransform完整代码总结 上一篇文章 Compose Canvas基础&#xff08;1&#xff09; drawxxx方法 前言 阅读本文需要一定compose基…

mysql——面试题初体验

查询环境 1、student&#xff08;学生表&#xff09; 2、课程表(course) 3、教师表(teacher) 4、成绩表(score) 问题 (1) 查询所有学生的学号、姓名、选课数、总成绩 mysql> select s.s_id as 学号,s.s_name as 姓名 from student as s; ---------------- | 学号 | 姓名…

E138: Can‘t write viminfo file

E138: Can’t write viminfo file /home/xxx/.viminfo! 原因 进入/home/xxx/目录下&#xff0c;用ls -a你会发现有很多.viminfa.tmp - .viminfz.tmp 这种的临时文件&#xff0c;这是因为使用vim编辑器时&#xff0c;如果编辑器没有正常退出就会生成一个暂存文件&#xff0c;…

Flow深入浅出系列之更聪明的分享 Kotlin Flows

Flow深入浅出系列之在ViewModels中使用Kotlin FlowsFlow深入浅出系列之更聪明的分享 Kotlin FlowsFlow深入浅出系列之使用Kotlin Flow自动刷新Android数据的策略 Flow深入浅出系列之更聪明的分享 Kotlin Flows 使生命周期对上游流有效&#xff0c;以跳过不必要的工作。这是一…

使用kaliber与imu_utils进行IMU、相机+IMU联合标定

目录 1 标定工具编译 1.1 IMU标定工具 imu_utils 1.2 相机标定工具 kaliber 2 标定数据录制 3 开始标定 3.1 IMU标定 3.2 相机标定 3.3 相机IMU联合标定 4 将参数填入ORBSLAM的文件中 1 标定工具编译 1.1 IMU标定工具 imu_utils 标定IMU我们使用imu_utils软件进行标定…

Variations-of-SFANet-for-Crowd-Counting记录

论文&#xff1a;Encoder-Decoder Based Convolutional Neural Networks with Multi-Scale-Aware Modules for Crowd Counting 论文链接&#xff1a;https://arxiv.org/abs/2003.05586 源码链接&#xff1a;GitHub - Pongpisit-Thanasutives/Variations-of-SFANet-for-Crowd-C…

yarn : 无法加载文件 C:\Program Files\nodejs\yarn.ps1

问题描述&#xff1a; 问题分析&#xff1a; 这个错误提示说明在电脑系统上禁止运行 PowerShell 脚本&#xff0c;因此导致无法加载 Yarn 的安装脚本。这是由于系统的执行策略&#xff08;Execution Policies&#xff09;设置所导致的。 解决方法&#xff1a; 1. 以管理员身…

Ubuntu中不能使用ifconfig命令

​ 问题 打开终端使用如下命令不能运行&#xff1a; ifconfig显示如下错误: 解决方法 在VMware中的虚拟机下面打开“编辑虚拟机设置”&#xff0c;或者在已经打开的虚拟机面板上面打开“虚拟机—设置” 选择网络适配器&#xff0c;选择“NAT模式”&#xff0c;没开机的就…

Learning Sample Relationship for Exposure Correction 论文阅读笔记

这是中科大发表在CVPR2023的一篇论文&#xff0c;提出了一个module和一个损失项&#xff0c;能够提高现有exposure correction网络的性能。这已经是最近第三次看到这种论文了&#xff0c;前两篇分别是CVPR2022的ENC&#xff08;和这篇文章是同一个一作作者&#xff09;和CVPR20…

ardupilot开发 --- 起飞前后 篇

起飞前检查 电机响应是否正确&#xff08;转向&#xff09;姿态响应是否正常&#xff08;roll pitch yaw&#xff09;GPS数据是否正常&#xff08;星数&#xff0c;RTK信号&#xff09;电源电压安全开关安全检测&#xff08;armed pre check&#xff09; 起飞前的必调参数 机…

mmlab 做实验

首先 下载项目完整代码&#xff0c;在pycharm中打开 1. comfig 中有各种网络模型&#xff0c;可以直接使用训练好的预训练模型&#xff0c;尽量不要改动网络模型的结构 2. 18表示网络机构18层&#xff0c;8是每个卡的batch&#xff0c;cifar10 是数据集 3.配置文件解析 4. …

工业机器视觉系统构成及功能

工业机器视觉系统构成及功能 工业机器视觉系统由光源、光学传感器、图像采集设备、图像处理设备、机器视觉软件、辅助传感器、控制单元和执行机构等组件构成。 光源提供光线以辅助图像获取。 光学传感器将外部场景转换为电信号。 图像采集设备将信号转换为图像数据&#xf…

VSCode连接代理

VSCode连接代理 首先有代理 然后在设置里搜代理 然后再在windows的设置–>网络–>代理 拼接上就行 最后重启

【小尘送书-第八期】《小团队管理:如何轻松带出1+1>2的团队》

大家好&#xff0c;我是小尘&#xff0c;欢迎你的关注&#xff01;大家可以一起交流学习&#xff01;欢迎大家在CSDN后台私信我&#xff01;一起讨论学习&#xff0c;讨论如何找到满意的工作&#xff01; &#x1f468;‍&#x1f4bb;博主主页&#xff1a;小尘要自信 &#x1…

macos 12 支持机型 macOS Monterey 更新中新增的功能

macOS Monterey 能让你以全然一新的方式与他人沟通联络、共享内容和挥洒创意。尽享 FaceTime 通话新增的音频和视频增强功能&#xff0c;包括空间音频和人像模式。通过功能强大的效率类工具&#xff08;例如专注模式、快速备忘录和 Safari 浏览器中的标签页组&#xff09;完成更…

【unity】【VR】白马VR课堂系列-VR开发核心基础04-主体设置-XR Rig的引入和设置

接下来我们开始引入并构建XR Rig。 你可以将XR Rig理解为玩家在VR世界中的替身。 我们先删除Main Camera&#xff0c;在Hierarchy右键点击删除。 然后再在场景层右键选择XR下的XR Origin。这时一个XR Origin对象就被添加到了Hierarchy。 重设XR Origin的Position和Rotation…

数据结构 - 4(栈和队列6000字详解)

一&#xff1a;栈 1.1 栈的概念 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原…

JVM三色标记

三色标记 什么是三色标记法 三色标记法&#xff0c;也被称为Tri-color Marking Algorithm&#xff0c;是一种用于追踪对象存活状态的垃圾回收算法。它基于William D. Hana和Mark S. McCulleghan在1976年提出的两色标记法的基础上进行了改进。 与两色标记法只能将对象标记为“…