Leetcode.174 地下城游戏
题目链接
Leetcode.174 地下城游戏
hard
题目描述
恶魔们抓住了公主并将她关在了地下城 d u n g e o n dungeon dungeon 的 右下角 。地下城是由 m x n
个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 0 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0 0 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1:
输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出:7
解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。
示例 2:
输入:dungeon = [[0]]
输出:1
提示:
- m = d u n g e o n . l e n g t h m = dungeon.length m=dungeon.length
- n = d u n g e o n [ i ] . l e n g t h n = dungeon[i].length n=dungeon[i].length
- 1 ≤ m , n ≤ 200 1 \leq m, n \leq 200 1≤m,n≤200
- − 1000 ≤ d u n g e o n [ i ] [ j ] ≤ 1000 -1000 \leq dungeon[i][j] \leq 1000 −1000≤dungeon[i][j]≤1000
解法:动态规划
假设我们考虑从左上角到右下角,这样的话我们需要考虑两个因素:当前路径和 ,当前路径上的最小路径和。因为存在两个同等重要的因素,所以我们无法确定下一个位置。
既然从左上角到右下角不行,那么我们就考虑从右下角到左上角。
考虑从右下角到左上角,我们定义 f ( i , j ) f(i,j) f(i,j) 为从位置 ( i , j ) (i,j) (i,j) 到终点 ( m − 1 , n − 1 ) (m-1,n-1) (m−1,n−1)所需要的最低初始健康点数。按照定义,最终我们返回的结果就是 f ( 0 , 0 ) f(0,0) f(0,0)。
f ( i , j ) f(i,j) f(i,j) 只与 f ( i + 1 , j ) f(i + 1,j) f(i+1,j) 和 f ( i , j + 1 ) f(i,j+1) f(i,j+1) 以及 d u n g e o n [ i ] [ j ] dungeon[i][j] dungeon[i][j] 有关。
即 f ( i , j ) = m i n { f [ i + 1 ] [ j ] , f [ i ] [ j + 1 ] } − d u n g e o n [ i ] [ j ] f(i,j) = min \{ f[i + 1][j] , f[i][j + 1] \} - dungeon[i][j] f(i,j)=min{f[i+1][j],f[i][j+1]}−dungeon[i][j]。
因为 f [ i ] [ j ] f[i][j] f[i][j] 必须是 ≥ 1 \geq1 ≥1 的,所以最终的转移方程为:
f ( i , j ) = m a x { m i n ( f [ i + 1 ] [ j ] , f [ i ] [ j + 1 ] ) − d u n g e o n [ i ] [ j ] , 1 } f(i,j) = max \{ min ( f[i + 1][j] , f[i][j + 1] ) - dungeon[i][j],1\} f(i,j)=max{min(f[i+1][j],f[i][j+1])−dungeon[i][j],1}
当 i = m − 1 i =m - 1 i=m−1 或者 j = n − 1 j = n- 1 j=n−1时, f [ i + 1 ] [ j ] f[i+1][j] f[i+1][j] 和 f [ i ] [ j + 1 ] f[i][j+1] f[i][j+1] 就会分别越界。初始直接定义 f [ i ] [ j ] f[i][j] f[i][j] 为一个较大的值,这里我设置的是 1 0 9 10^9 109。
特别需要注意的是,我们直接把 f [ m ] [ n − 1 ] f[m][n-1] f[m][n−1] 和 f [ m − 1 ] [ n ] f[m-1][n] f[m−1][n] 设置为 1 1 1,这样是为了让 f [ m − 1 ] [ n − 1 ] = d u n g e o n [ m − 1 ] [ n − 1 ] f[m-1][n-1] = dungeon[m-1][n-1] f[m−1][n−1]=dungeon[m−1][n−1]。
时间复杂度: O ( m × n ) O(m \times n) O(m×n)
C++代码:
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& g) {int m = g.size() , n = g[0].size();vector<vector<int>> f(m + 1,vector<int>(n + 1,1e9));f[m][n - 1] = 1;f[m - 1][n] = 1;for(int i = m - 1;i >= 0;i--){for(int j = n - 1;j >= 0;j--){int t = min(f[i + 1][j],f[i][j + 1]);f[i][j] = max(t - g[i][j] , 1);}}return f[0][0];}
};
相关文章:

Leetcode.174 地下城游戏
题目链接 Leetcode.174 地下城游戏 hard 题目描述 恶魔们抓住了公主并将她关在了地下城 d u n g e o n dungeon dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公…...

python实现adb辅助点击屏幕工具
#!/usr/bin/env python # -*- coding: utf-8 -*-import re import os import time import subprocess import tkinter as tk from tkinter import messagebox from PIL import Image, ImageTk# 设置ADB路径(根据你的系统和安装路径进行调整) ADB_PATH C…...

智能合约安全分析,针对 ERC777 任意调用合约 Hook 攻击
智能合约安全分析,针对 ERC777 任意调用合约 Hook 攻击 Safful发现了一个有趣的错误,有可能成为一些 DeFi 项目的攻击媒介。这个错误尤其与著名的 ERC777 代币标准有关。此外,它不仅仅是众所周知的黑客中常见的简单的重入问题。 这篇文章对 …...
nodejs 爬虫 axios 异步爬虫 教程 【一】
axios 自定义headers axios.defaults.headers.common["User-Agent"] "Googlebot/2.1 (http://www.google.com/bot.html)"; 运行环境: node :v18 const axios require("axios"); axios.defaults.headers.common["U…...
Swift学习笔记三(Dictionary 篇)
1 Dictionary 概念 字典储存无序的互相关联的同一类型的键和同一类型的值的集合。字典类型的全写方式 Dictionary<Key, Value>,简写方式 [Key: Value],建议使用简写方式。字典的 key 必须是可哈希的。 2 Dictionary创建 2.1 初始器创建方式 2.2 …...
javax.mail 遇到501 mail from address must be same as authorization user 的問題
使用不同的兩個帳戶发送email时,第一个账户可以发送成功,但到第二个账户的时候就报出了501 mail from address must be same as authorization user的错误。 具体代码如下: import java.util.Date; import java.util.List; import java.util.…...

【Python】网络编程
Socket Socket (简称 套接字)是进程之间通信一个工具,进程之间想要进行网络通信需要socket。Socket负责进程之间的网络数据传输,好比数据的搬运工。 客户端和服务端 2个进程之间通过Socket进行相互通讯,就必须有服务端和客户端 Socket服务…...
客户端开发常用框架
在Unity游戏开发中,客户端常用的框架包括以下几种: 1.Unity的网络框架:Unity自带了网络框架,包括Unity Networking、Unity Matchmaker和Unity Remote等。这些框架可以帮助我们进行游戏的联机对战、排行榜、跨平台等功能的设计和实…...

数据分析综述
⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据…...

区块链技术与应用 - 学习笔记2【密码学基础】
大家好,我是比特桃。本系列笔记只专注于探讨研究区块链技术原理,不做其他违反相关规定的讨论。 区块链技术已被纳入国家十四五规划,在“加快数字发展 建设数字中国”篇章中,区块链被列为“十四五”七大数字经济重点产业之一&#…...
制作Linux发行版安装镜像:复刻centos镜像安装ISO
制作Linux发行版安装镜像:复刻centos镜像安装ISO 我们平时经常下载Linux各个发行版,下载ISO,安装使用。那么ISO到底是如何制作的?安装过程是什么原理? 近来打算讲镜像制作的过程、原理,通过一个专栏分享一…...
【复习socket】每天40min,我们一起用70天稳扎稳打学完《JavaEE初阶》——29/70 第二十九天
专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录) 文章字体风格: 红色文字表示:重难点★✔ 蓝色文字表示:思路以及想法★✔ 如果大家觉得有帮助的话,感谢大家帮忙 点…...
postgresql-常用数学函数
postgresql-常用数学函数 案例 案例 --求余 1 select 5%2 as t; --绝对值 17.4 select abs(-17.4) as t2; -- 大于等于最小整数 -42 select ceil(-42.8) as t3; -- 小于等于的最大整数 42 select floor(42.3) as t4; -- 四舍五入 44 select round(43.6) as t5; -- 向零取整 12…...
Docker实战技巧(一):常用命令与最佳实践
一、原理 1、Hypervisor是一种运行在物理服务器和操作系统之间的中间软件层,可允许多个操作系统和应用共享一套基础物理硬件,它能直接访问物理设备,会给每一台虚拟机分配内存、CPU、网络、磁盘等资源,也可以确保虚拟机对应的硬…...

使用CUDA计算GPU的理论显存带宽
文章目录 一、显存带宽和理论显存带宽1. 显存带宽2. 理论显存带宽1)计算公式2)举例 二、利用CUDA计算理论显存带宽 一、显存带宽和理论显存带宽 1. 显存带宽 显存带宽是指显存和GPU计算单元之间的数据传输速率。 显存带宽越大,意味着数据传…...

npm install依赖冲突解决办法
今天npm的时候发现报错,原来是依赖冲突了 npm后面加上这个指令就可以顺利的安装依赖了。问题主因就是不同开发用了不同版本node导致依赖版本不同,出现了成功冲突,这是段指令;它告诉npm忽略项目中引入的各个依赖模块之间依赖相同但…...
植物大战僵尸各种僵尸攻略
前言 此文章为“植物大战僵尸”专栏中的009刊(2023年9月第八刊),欢迎订阅。版权所有。 注意: 1.本博客适用于pvz无名版; 2.pvz指植物大战僵尸(Plants VS Zonbies); 3.本文以耗费低做标准&am…...
Scrum敏捷开发企业实战培训
课程简介 Scrum是目前运用最为广泛的敏捷开发方法,是一个轻量级的项目管理和产品研发管理框架。 这是一个两天的实训课程,面向研发管理者、项目经理、产品经理、研发团队等,旨在帮助学员全面系统地学习Scrum和敏捷开发, 帮助企业快速启动敏…...

uniapp 下拉框数据回显的问题
问题 : 现在是下拉框数据回显不了, 绑定的v-model 原因 : uniui 下拉框数据绑定要是 value text 这种格式的 解决办法: 将获取到的后端数据 转换为 需要的格式 ,再进行绑定 下拉框的数据 遍历...
使用php 获取时间今天、明天、昨天时间戳的详解
使用php获取时间今、明天、昨天时间戳 <?php echo "今天:".date("Y-m-d").""; echo "昨天:".date("Y-m-d",strtotime("-1 day")), ""; echo "明天:".date("Y-m-d&qu…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...