「动态规划」如何求地下城游戏中,最低初始健康点数是多少?

2024-06-07 21:44

本文主要是介绍「动态规划」如何求地下城游戏中,最低初始健康点数是多少?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

174. 地下城游戏icon-default.png?t=N7T8https://leetcode.cn/problems/dungeon-game/description/

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


我们用动态规划的思想来解决这个问题。

确定状态表示:根据经验和题目要求,我们有2个状态表示的方案:

  • 用dp[i][j]表示:从起点开始,到达[i, j]位置,所需的最低初始健康点数。
  • 用dp[i][j]表示:从[i, j]位置开始,到达终点,所需的最低初始健康点数。

究竟选择哪一种状态表示呢?事实上,哪一种状态表示能推导出状态转移方程,我们就选择哪一种状态表示。

推导状态转移方程:首先考虑前一种状态表示。考虑最近的一步,要想到达[i, j]位置,只有2种情况:

  • 先到达[i - 1, j]位置,再向下走一步,到达[i, j]位置。
  • 先到达[i, j - 1]位置,再向右走一步,到达[i, j]位置。

如果能推出状态转移方程,那么状态转移方程一定形如dp[i][j] = f(dp[i - 1, j], dp[i, j - 1])。然而,[i, j]右下方的位置是有可能影响到dp[i][j]的。比如,如果右下方有一个房间是-1000,那么所需的初始健康点数就是一个很大的值;如果右下方都是正数,那么可能不需要很大的初始健康点数。也就是说,dp[i][j]和右下方的值相关,但是dp[i][j] = f(dp[i - 1, j], dp[i, j - 1])这个方程与右下方的值无关。从而,我们推导不出状态转移方程。

所以,我们选择后一种状态表示:用dp[i][j]表示:从[i, j]位置开始,到达终点,所需的最低初始健康点数。考虑最近的一步,要想从dp[i][j]位置出发到达终点,只有2种情况:

  • 先向下走一步,到达[i + 1, j]位置,再从[i + 1, j]位置出发到达终点。所以,从[i, j]位置出发到达终点需要的最低初始健康点数dp[i][j],在经历了[i, j]房间后,健康点数变为dp[i][j] + dungeon[i][j],而dp[i][j] + dungeon[i][j]必须至少是从[i + 1, j]位置出发到达终点所需要的最低初始健康点数dp[i + 1][j],即dp[i][j] + dungeon[i][j] >= dp[i + 1][j],从而dp[i][j] >= dp[i + 1][j] - dungeon[i][j],又由于dp[i][j]表示最低初始健康点数,所以dp[i][j] = dp[i + 1][j] - dungeon[i][j]。
  • 先向右走一步,到达[i, j + 1]位置,再从[i, j + 1]位置出发到达终点。同理可得此时dp[i][j] = dp[i][j + 1] - dungeon[i][j]。

从[i, j]位置出发到达终点所需要的最低初始健康点数,应该是上面2种情况的较小值,即dp[i][j] = min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j]) = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。

然而这个状态转移方程有个很大的漏洞。如果min(dp[i + 1][j], dp[i][j + 1]) <= dungeon[i][j],那么dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j] <= 0。然而血量是不能低于0的,所以我们还需要判断一下,如果计算出来的dp[i][j] <= 0,那么dp[i][j] = 1。

综上所述:状态转移方程为:dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])

初始化:观察状态转移方程,我们在计算dp表最后一行和最后一列的值时,会越界访问。所以,我们要对其初始化。这里我们用增加辅助结点的方式来初始化。我们在dp表的最下面和最右边分别加上一行一列辅助结点。接下来我们考虑,如何初始化辅助结点,才能保证后续的填表是正确的。我们把此时的dp表画出来:

      ? *? *
? ? ? ? *
* * * * *

先考虑右下角的?位置。这个?位置表示,直接从dungeon的右下角出发,到达右下角,所需要的最低初始健康点数。显然这个?位置的值只需要保证,在更新完处于dungeon的右下角的健康点数之后,其值依然大于等于1,也就是说,如果dungeon的右下角是正数,那么?位置的值是1;如果dungeon的右下角是负数,那么?位置的值是1减去dungeon的右下角的值(负负得正)。再观察状态转移方程:dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]),我们发现,如果dp[i + 1][j] = dp[i][j + 1] = 1,那么dp[i][j] = max(1, min(1, 1) - dungeon[i][j]) = max(1, 1 - dungeon[i][j]),1代表dungeon的右下角是正数的情况,1 - dungeon[i][j]代表dungeon的右下角是负数的情况,刚好符合预期。所以,对于右下角的?位置,我们要把它的下面和右边的2个*位置的值初始化为1。

      ? *? *
? ? ? ? 1
* * * 1 *

接着考虑除了右下角的?位置之外,其余的?位置。观察状态转移方程: dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]),我们发现,dp[i + 1][j]和dp[i][j + 1]会涉及到辅助结点。我们只需要把这些辅助结点初始化为+∞,在计算min(dp[i + 1][j], dp[i][j + 1])时,辅助结点的值就不会影响到结果了。由于并没有导致溢出风险的运算,我们用INT_MAX代表+∞即可。

综上所述:我们在dp表的最下面和最右边分别加上一行一列辅助结点,并且把[m - 1, n]和[m, n - 1]位置的值初始化为1,其余辅助结点初始化为INT_MAX

填表顺序:根据状态转移方程,dp[i][j]依赖于dp[i + 1][j]和dp[i][j + 1],所以应从下往上,从右往左填表

返回值:应返回dp表左上角的值,即dp[0][0]

细节问题:由于新增了一行一列辅助结点,dp表的规模比dungeon的规模大一行一列,即dp表的规模为(m + 1) x (n + 1)。由于辅助结点是在dp表的右下方,并不影响下标的映射关系,所以dp表的[i, j]位置依然对应dungeon的[i, j]位置。

时间复杂度:O(m x n),空间复杂度:O(m x n)。

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();// 创建dp表vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));// 初始化dp[m - 1][n] = dp[m][n - 1] = 1;// 填表for (int i = m - 1; i >= 0; i--) {for (int j = n - 1; j >= 0; j--) {dp[i][j] =max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);}}// 返回结果return dp[0][0];}
};

这篇关于「动态规划」如何求地下城游戏中,最低初始健康点数是多少?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1040384

相关文章

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法,代码不进

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要