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];}
};

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

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

相关文章

【高阶产品策略】设计有效的AB测试

文章目录 1、A/B测试概述2、A/B测试实施过程3、A/B测试中需要注意的地方4、从一个案例中看A/B测试 1、A/B测试概述 2、A/B测试实施过程 3、A/B测试中需要注意的地方 4、从一个案例中看A/B测试

编写中间件以用于 Express 应用程序

概述 中间件函数能够访问请求对象 (req)、响应对象 (res) 以及应用程序的请求/响应循环中的下一个中间件函数。下一个中间件函数通常由名为 next 的变量来表示。 中间件函数可以执行以下任务&#xff1a; 执行任何代码。对请求和响应对象进行更改。结束请求/响应循环。调用堆…

pytorch学习——循环神经网络RNN讲解及其实现

参考书籍&#xff1a;8.6. 循环神经网络的简洁实现 — 动手学深度学习 2.0.0 documentation 参考视频&#xff1a;54 循环神经网络 RNN【动手学深度学习v2】_哔哩哔哩_bilibili 一.介绍 循环神经网络RNN&#xff08;Recurrent Neural Network &#xff09;是一类广泛应用于序列…

stm32之30.DMA

DMA&#xff08;硬件加速方法&#xff09;一般用于帮运比较大的数据&#xff08;如&#xff1a;摄像头数据图像传输&#xff09;&#xff0c;寄存器-》DMA-》RAM 或者 RAM-》DMA-》寄存器提高CPU的工作效率 源码-- #include "myhead.h" #include "adc.h"#…

javaee之黑马乐优商城2

简单分析一下商品分类表的结构 先来说一下分类表与品牌表之间的关系 再来说一下分类表和品牌表与商品表之间的关系 面我们要开始就要创建sql语句了嘛&#xff0c;这里我们分析一下字段 用到的数据库是heima->tb_category这个表 现在去数据库里面创建好这张表 下面我们再去编…

有向图和无向图的表示方式(邻接矩阵,邻接表)

目录 一.邻接矩阵 1.无向图​编辑 2.有向图 补充&#xff1a;网&#xff08;有权图&#xff09;的邻接矩阵表示法 二.邻接表 1.无向图 2.有向图 三.邻接矩阵与邻接表的关系 一.邻接矩阵 1.无向图 &#xff08;1&#xff09;对角线上是每一个顶点与自身之间的关系&…

线性空间和线性变化

目录 考点一、线性空间的基与维数 1、线性空间 2、基底 3、子空间&#xff08;线性子空间&#xff09; ​编辑4、生成子空间 &#xff08;1&#xff09;、v1 n v2 &#xff08;2&#xff09;、v1 v2 5、求和子空间的方法 6、维数定理 7、例题 &#xff08;1&#xf…

HCIA自学笔记01-冲突域

共享式网络&#xff08;用同一根同轴电缆通信&#xff09;中可能会出现信号冲突现象。 如图是一个10BASE5以太网&#xff0c;每个主机都是用同一根同轴电缆来与其它主机进行通信&#xff0c;因此&#xff0c;这里的同轴电缆又被称为共享介质&#xff0c;相应的网络被称为共享介…

MyBatis-Plus学习笔记总结

一、查询 构造器分为QueryWrapper和LambdaQueryWrapper 创建实体类User package com.system.mybatisplus.model;import com.baomidou.mybatisplus.annotation.IdType; import com.baomidou.mybatisplus.annotation.TableField; import com.baomidou.mybatisplus.annotation.…

JDK8的 ConcurrentHashMap 源码分析

目录 1. 导读 2. ConcurrentHashMap 成员变量解读 3. ConcurrentHashMap 初始化 3.1 ConcurrentHashMap 无参构造源码解读 3.2 ConcurrentHashMap 带参构造源码解读 3.3 tableSizeFor 方法作用解读 3.4 ConcurrenthashMap初始化总结 4. ConcurrentHashMap 添加元素方法…

springboot之一:配置文件(内外部配置优先顺序+properties、xml、yaml基础语法+profile动态切换配置、激活方式)

配置的概念&#xff1a; Spring Boot是基于约定的&#xff0c;所以很多配置都有默认值&#xff0c;但如果想使用自己的配置替换默认配置的话&#xff0c;就可以使用application.properties或者application.yml(application.yaml)进行配置。 注意配置文件的命名必须是applicat…

大数据课程K18——Spark的ALS算法与显式矩阵分解

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Spark的ALS算法与显式矩阵分解; ⚪ 掌握Spark的ALS算法原理; 一、ALS算法与显式矩阵分解 1. 概述 我们在实现推荐系统时,当要处理的那些数据是由用户所提供的自身的偏好数据,这些…

设计模式系列-原型模式

一、上篇回顾 上篇创建者模式中&#xff0c;我们主要讲述了创建者的几类实现方案&#xff0c;和创建者模式的应用的场景和特点&#xff0c;创建者模式适合创建复杂的对象&#xff0c;并且这些对象的每 个组成部分的详细创建步骤可以是动态的变化的&#xff0c;但是每个对象的组…

数据可视化、BI和数字孪生软件:用途和特点对比

在现代企业和科技领域&#xff0c;数据起着至关重要的作用。为了更好地管理和理解数据&#xff0c;不同类型的软件工具应运而生&#xff0c;其中包括数据可视化软件、BI&#xff08;Business Intelligence&#xff09;软件和数字孪生软件。虽然它们都涉及数据&#xff0c;但在功…

《TCP/IP网络编程》阅读笔记--域名及网络地址

目录 1--域名系统 2--域名与 IP 地址的转换 2-1--利用域名来获取 IP 地址 2-2--利用 IP 地址获取域名 3--代码实例 3-1--gethostbyname() 3-2--gethostbyaddr() 1--域名系统 域名系统&#xff08;Domain Name System&#xff0c;DNS&#xff09;是对 IP 地址和域名进行相…

2023/9/7 -- C++/QT

作业 1> 思维导图 2> 封装一个结构体&#xff0c;结构体中包含一个私有数组&#xff0c;用来存放学生的成绩&#xff0c;包含一个私有变量&#xff0c;用来记录学生个数&#xff0c; 提供一个公有成员函数&#xff0c;void setNum(int num)用于设置学生个数 提供一个…

✔ ★算法基础笔记(Acwing)(一)—— 基础算法(20道题)【java版本】

基础算法 一、快速排序1. 快速排序例题2. 第k个数( 快速选择 ) ✔ ✔1.31★快排二刷总结( 4点 ) 二、归并排序1. 归并排序模板题 ✔ ✔1.31★二刷总结 ★2. 逆序对的数量 ✔ ✔1.31★二刷总结 三、二分1. 数的范围 ✔1.31★二刷总结(mid > x 则是 输出最左边一个)第一个大于…

Oracle数据库开发者工具

和开发者相关的数据库特性&#xff0c;功能与工具列举如下&#xff0c;但不限于以下。因为Oracle数据库中的许多功能其实都间接的和开发者发生关系&#xff0c;如Oracle高级安全选件中的透明数据加密&#xff0c;数据编辑。Oracle Spatial and Graph&#xff08;地理空间与图&a…

latex修改公式的默认编号

文章目录 问题描述省流出错演示没有载入amsmath包载入amsmath包 总结 问题描述 有时想自己定义公式的编号&#xff0c;不想用默认的编号(1) (2)…&#xff0c;我们应该怎么做呢&#xff1f; 只需看本文一分钟就能解决。 省流 开头载入amsmath包&#xff0c;然后在公式后面加…

算法——组合程序算法解析

组合就是从m个元素的数组中求n个元素的所有组合&#xff0c;代码如下&#xff1a; #include <iostream> #include <vector> using namespace std; // 递归求解组合 void combinations(vector<int>& nums, vector<int>& combination, int star…