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

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 1m,n200
  • − 1000 ≤ d u n g e o n [ i ] [ j ] ≤ 1000 -1000 \leq dungeon[i][j] \leq 1000 1000dungeon[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) (m1,n1)所需要的最低初始健康点数。按照定义,最终我们返回的结果就是 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=m1 或者 j = n − 1 j = n- 1 j=n1时, 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][n1] f [ m − 1 ] [ n ] f[m-1][n] f[m1][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[m1][n1]=dungeon[m1][n1]

时间复杂度: 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 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里&#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公…...

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路径&#xff08;根据你的系统和安装路径进行调整&#xff09; ADB_PATH C…...

智能合约安全分析,针对 ERC777 任意调用合约 Hook 攻击

智能合约安全分析&#xff0c;针对 ERC777 任意调用合约 Hook 攻击 Safful发现了一个有趣的错误&#xff0c;有可能成为一些 DeFi 项目的攻击媒介。这个错误尤其与著名的 ERC777 代币标准有关。此外&#xff0c;它不仅仅是众所周知的黑客中常见的简单的重入问题。 这篇文章对 …...

nodejs 爬虫 axios 异步爬虫 教程 【一】

axios 自定义headers axios.defaults.headers.common["User-Agent"] "Googlebot/2.1 (http://www.google.com/bot.html)"; 运行环境&#xff1a; node &#xff1a;v18 const axios require("axios"); axios.defaults.headers.common["U…...

Swift学习笔记三(Dictionary 篇)

1 Dictionary 概念 字典储存无序的互相关联的同一类型的键和同一类型的值的集合。字典类型的全写方式 Dictionary<Key, Value>&#xff0c;简写方式 [Key: Value]&#xff0c;建议使用简写方式。字典的 key 必须是可哈希的。 2 Dictionary创建 2.1 初始器创建方式 2.2 …...

javax.mail 遇到501 mail from address must be same as authorization user 的問題

使用不同的兩個帳戶发送email时&#xff0c;第一个账户可以发送成功&#xff0c;但到第二个账户的时候就报出了501 mail from address must be same as authorization user的错误。 具体代码如下&#xff1a; import java.util.Date; import java.util.List; import java.util.…...

【Python】网络编程

Socket Socket (简称 套接字)是进程之间通信一个工具&#xff0c;进程之间想要进行网络通信需要socket。Socket负责进程之间的网络数据传输&#xff0c;好比数据的搬运工。 客户端和服务端 2个进程之间通过Socket进行相互通讯&#xff0c;就必须有服务端和客户端 Socket服务…...

客户端开发常用框架

在Unity游戏开发中&#xff0c;客户端常用的框架包括以下几种&#xff1a; 1.Unity的网络框架&#xff1a;Unity自带了网络框架&#xff0c;包括Unity Networking、Unity Matchmaker和Unity Remote等。这些框架可以帮助我们进行游戏的联机对战、排行榜、跨平台等功能的设计和实…...

数据分析综述

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…...

区块链技术与应用 - 学习笔记2【密码学基础】

大家好&#xff0c;我是比特桃。本系列笔记只专注于探讨研究区块链技术原理&#xff0c;不做其他违反相关规定的讨论。 区块链技术已被纳入国家十四五规划&#xff0c;在“加快数字发展 建设数字中国”篇章中&#xff0c;区块链被列为“十四五”七大数字经济重点产业之一&#…...

制作Linux发行版安装镜像:复刻centos镜像安装ISO

制作Linux发行版安装镜像&#xff1a;复刻centos镜像安装ISO 我们平时经常下载Linux各个发行版&#xff0c;下载ISO&#xff0c;安装使用。那么ISO到底是如何制作的&#xff1f;安装过程是什么原理&#xff1f; 近来打算讲镜像制作的过程、原理&#xff0c;通过一个专栏分享一…...

【复习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是一种运行在物理服务器和操作系统之间的中间软件层&#xff0c;可允许多个操作系统和应用共享一套基础物理硬件&#xff0c;它能直接访问物理设备&#xff0c;会给每一台虚拟机分配内存、CPU、网络、磁盘等资源&#xff0c;也可以确保虚拟机对应的硬…...

使用CUDA计算GPU的理论显存带宽

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

npm install依赖冲突解决办法

今天npm的时候发现报错&#xff0c;原来是依赖冲突了 npm后面加上这个指令就可以顺利的安装依赖了。问题主因就是不同开发用了不同版本node导致依赖版本不同&#xff0c;出现了成功冲突&#xff0c;这是段指令&#xff1b;它告诉npm忽略项目中引入的各个依赖模块之间依赖相同但…...

植物大战僵尸各种僵尸攻略

前言 此文章为“植物大战僵尸”专栏中的009刊&#xff08;2023年9月第八刊&#xff09;&#xff0c;欢迎订阅。版权所有。 注意&#xff1a; 1.本博客适用于pvz无名版&#xff1b; 2.pvz指植物大战僵尸&#xff08;Plants VS Zonbies)&#xff1b; 3.本文以耗费低做标准&am…...

Scrum敏捷开发企业实战培训

课程简介 Scrum是目前运用最为广泛的敏捷开发方法&#xff0c;是一个轻量级的项目管理和产品研发管理框架。 这是一个两天的实训课程&#xff0c;面向研发管理者、项目经理、产品经理、研发团队等&#xff0c;旨在帮助学员全面系统地学习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…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...