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

LeetCode刷题--- 地下城游戏

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

 http://t.csdnimg.cn/yUl2I

【C++】    

​​​​​​http://t.csdnimg.cn/6AbpV

数据结构与算法

 ​​​http://t.csdnimg.cn/hKh2l


前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


地下城游戏

题目链接:地下城游戏

题目

恶魔们抓住了公主并将她关在了地下城 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

解法

算法原理讲解

我们这题使用动态规划,我们做这类题目可以分为以下五个步骤

  1. 状态显示
  2. 状态转移方程
  3. 初始化(防止填表时不越界)
  4. 填表顺序
  5. 返回值
  • 状态显示
  1. 这道题如果我们和以前的题目一样定义成:从起点开始,到达 [i, j] 位置的时候,所需的最低初始健康点数。 那么我们分析状态转移的时候会有⼀个问题:那就是我们当前的健康点数还会受到后⾯的路径的影响。也就是从上往下的状态转移不能很好地解决问题。
  2. 这个时候我们要换⼀种状态表示:从 [i, j] 位置出发,到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候,后续的最佳状态就已经知晓。 综上所述,定义状态表示为: dp[i][j] 表示:从 [i, j] 位置出发,到达终点时所需的最低初始健康点数。
  • 状态转移方程
对于 dp[i][j] ,从 [i, j] 位置出发,下⼀步会有两种选择(为了⽅便理解,设 dp[ i ][ j ] 的最终答案是 x
  • 走到右边,然后⾛向终点 。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要大于等于右边位 置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i][j + 1] 。 通过移项可得: x >= dp[i][j + 1] - dungeon[i][j] 。因为我们要的是最小值,因此这种情况下的 x = dp[i][j + 1] - dungeon[i][j]
  • ⾛到下边,然后⾛向终点。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要⼤于等于下边位置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i + 1][j] 。 通过移项可得: x >= dp[i + 1][j] - dungeon[i][j] 。因为我们要的是最小值,因此这种情况下的 x = dp[i + 1][j] -dungeon[i][j]
综上所述,我们需要的是两种情况下的最⼩值,因此可得状态转移⽅程为:
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
但是,如果当前位置的 dungeon[i][j] 是⼀个⽐较⼤的正数的话, dp[i][j] 的值可能变成 0 或者负数。也就是最低点数会⼩于 1 ,那么骑⼠就会死亡。因此我们求出来的 dp[i][j] 如果⼩于等于 0 的话,说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i][j] 与 1 取⼀个最⼤值即可: dp[i][j] = max(1, dp[i][j])。
  • 初始化(防止填表时不越界)
dp 表最后⾯添加⼀⾏,并且添加⼀列后,所有的值都先初始化为⽆穷⼤,然后让 dp[m][n - 1] = dp[m - 1][n] = 1 即可。
  • 填表顺序
根据「状态转移⽅程」,我们需要「从下往上填每⼀⾏」,「每⼀⾏从右往左」。
  • 返回值
根据「状态表⽰」,我们需要返回 dp[0][0] 的值。

代码实现

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size();int n = dungeon[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1,INT_MAX));// 初始化dp[m][n-1] = dp[m-1][n] = 1;// 填表for (int i = m - 1; i >= 0; i--){for (int j = n - 1; j >=0; j--){dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];dp[i][j] = max(1,dp[i][j]);     // 防止正数太大}}return dp[0][0];}
};

相关文章:

LeetCode刷题--- 地下城游戏

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 ​​​​​​http://t.csdnimg.cn/6AbpV 数据结构与算法 ​​​http://t.csdnimg.cn/hKh2l 前言&#xff1a;这个专栏主要讲述动…...

【sklearn练习】鸢尾花

一、 import numpy as np from sklearn import datasets from sklearn.model_selection import train_test_split from sklearn.neighbors import KNeighborsClassifier 第二行&#xff1a;导入datasets数据集 第三行&#xff1a;train_test_split 的作用是将数据集随机分配…...

STM32的USB设备库

适用范围&#xff1a;“on the STM32F10xxx,STM32F37xxx, STM32F30xxx and STM32L15xxx devices.” STM32_USB-FS-Device_Lib_V4.0.0.rar&#xff08;访问密码&#xff1a;1666&#xff09;https://url48.ctfile.com/f/33868548-1000799917-a5409d?p1666 适用范围&#xff1…...

整数对最小和(100%用例)C卷 (JavaPythonC++Node.jsC语言)

给定两个整数数组 array1 、 array2 ,数组元素按升序排列。假设从 array1 、 array2 中分别取出一个元素可构成一对元素,现在需要取出 k 对元素,并对取出的所有元素求和,计算和的最小值 注意:两对元素如果对应于 array1 、 array2 中的两个下标均相同,则视为同一对元素。…...

QT笔记 - 加载带有提升为自定义部件类的“.ui“文件 - 重写QUiLoader::createWidget()函数

说明 如果ui设计中有提升过小部件&#xff0c;则无法直接使用QUiLoader加载。完成加载需要重新实现UiLoader::createWidget()函数。 函数 virtual QWidget * QUiLoader::createWidget(const QString & className, QWidget * parent Q_NULLPTR, const QString & name…...

开启Android学习之旅-2-架构组件实现数据列表及添加(kotlin)

Android Jetpack 体验-官方codelab 1. 实现功能 使用 Jetpack 架构组件 Room、ViewModel 和 LiveData 设计应用&#xff1b;从sqlite获取、保存、删除数据&#xff1b;sqlite数据预填充功能&#xff1b;使用 RecyclerView 展示数据列表&#xff1b; 2. 使用架构组件 架构组…...

leetcode 动态规划(最后一块石头的重量II、目标和、一和零)

1049.最后一块石头的重量II 力扣题目链接(opens new window) 题目难度&#xff1a;中等 有一堆石头&#xff0c;每块石头的重量都是正整数。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 x < …...

JavaWeb-HTTP

一、概念 HTTP&#xff1a;HyperText Transfer Protocol&#xff0c;超文本传输协议。读者应该不是第一次接触这个名词&#xff0c;但可能仍然不是很理解&#xff0c;笔者将逐一解释。 HyperText&#xff08;超文本&#xff09;&#xff1a;根据维斯百科&#xff0c;Hypertex…...

算法训练营第四十二天|动态规划:01背包理论基础 416. 分割等和子集

目录 动态规划&#xff1a;01背包理论基础416. 分割等和子集 动态规划&#xff1a;01背包理论基础 文章链接&#xff1a;代码随想录 题目链接&#xff1a;卡码网&#xff1a;46. 携带研究材料 01背包问题 二维数组解法&#xff1a; #include <bits/stdc.h> using namesp…...

前端 JS篇快问快答

问题&#xff1a;常见的特殊字符&#xff08;不包括空格\s&#xff09; 正则表达式为&#xff1a; 回答&#xff1a;/[!#$%^&*()\-_{};:",.<>/?[\]~|]/ &#xff08;加粗的紫色字符都是特殊字符&#xff09; 问题&#xff1a;常见的特殊字符&#xff08;包括…...

vue/vue3/js来动态修改我们的界面浏览器上面的文字和图标

前言&#xff1a; 整理vue/vue3项目中修改界面浏览器上面的文字和图标的方法。 效果&#xff1a; vue2/vue3: 默认修改 public/index.html index.html <!DOCTYPE html> <html lang"en"><head><link rel"icon" type"image/sv…...

MobaXterm SSH 免密登录配置

文章目录 1.简介2.SSH 免密登录配置第一步&#xff1a;点击 Session第二步&#xff1a;选择 SSH第三步&#xff1a;输入服务器地址与用户名第四步&#xff1a;设置会话名称第五步&#xff1a;点击 OK 并输入密码 3.密码管理4.小结参考文献 1.简介 MobaXterm 是一个功能强大的终…...

霍兰德职业兴趣测试:找到与你性格匹配的职业

霍兰德职业兴趣理论 约翰霍兰德&#xff08;John Holland&#xff09;是美国约翰霍普金斯大学心理学教授&#xff0c;美国著名的职业指导专家。他于1959年提出了具有广泛社会影响的职业兴趣理论。认为人的人格类型、兴趣与职业密切相关&#xff0c;兴趣是人们活动的巨大动力&a…...

LVGL学习笔记 显示和隐藏 对象的属性标志位 配置

在显示GUI的过程中需要对某些对象进行临时隐藏或临时显示,因此需要对该对象的FLAG进行配置就可以实现对象的显示和隐藏了. 调用如下接口可以实现: lv_obj_add_flag(user_obj, LV_OBJ_FLAG_HIDDEN);//隐藏对象lv_obj_clear_flag(user_obj, LV_OBJ_FLAG_HIDDEN);//取消隐藏实现的…...

cuda上使用remap函数

在使用opencv中的remap函数时&#xff0c;发现运行时间太长了&#xff0c;如果使用视频流进行重映射时根本不能实时&#xff0c;因此只能加速 1.使用opencv里的cv::cuda::remap函数 cv::cuda::remap函数头文件是#include <opencv2/cudawarping.hpp>&#xff0c;编译ope…...

【JaveWeb教程】(18) MySQL数据库开发之 MySQL数据库设计-DDL 如何查询、创建、使用、删除数据库数据表 详细代码示例讲解

目录 2. 数据库设计-DDL2.1 项目开发流程2.2 数据库操作2.2.1 查询数据库2.2.2 创建数据库2.2.3 使用数据库2.2.4 删除数据库 2.3 图形化工具2.3.1 介绍2.3.2 安装2.3.3 使用2.2.3.1 连接数据库2.2.3.2 操作数据库 2.3 表操作2.3.1 创建2.3.1.1 语法2.3.1.2 约束2.3.1.3 数据类…...

ElasticSearch学习笔记-SpringBoot整合Elasticsearch7

项目最近需要接入Elasticsearch7&#xff0c;顺带记录下笔记。 Elasticsearch依赖包版本 <properties><elasticsearch.version>7.9.3</elasticsearch.version><elasticsearch.rest.version>7.9.3</elasticsearch.rest.version> </propertie…...

[足式机器人]Part2 Dr. CAN学习笔记 - Ch02动态系统建模与分析

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记 - Ch02动态系统建模与分析 1. 课程介绍2. 电路系统建模、基尔霍夫定律3. 流体系统建模4. 拉普拉斯变换&#xff08;Laplace&#xff09;传递函数、微分方程4.1 Laplace Transform 拉式变换4.2 收…...

【一周年创作总结】人生是远方的无尽旷野呀

那一眼瞥见的伟大的灵魂&#xff0c;却似模糊的你和我 文章目录 &#x1f4d2;各个阶段的experience&#x1f50e;大一寒假&#x1f50e;大一下学期&#x1f50e;大一暑假&#x1f50e;大二上学期&#xff08;现在&#xff09; &#x1f354;相遇CSDN&#x1f6f8;自媒体&#…...

金融帝国实验室(Capitalism Lab)V10版本游戏平衡性优化与改进

即将推出的V10版本中的各种游戏平衡性优化与改进&#xff1a; ————————————— 一、当玩家被提议收购一家即将破产的公司时&#xff0c;显示商业秘密。 当一家公司濒临破产&#xff0c;玩家被提议收购该公司时&#xff0c;如果玩家有兴趣评估该公司&#xff0c;则无…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...