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…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

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 …...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...