【Leetcode每日一题】 动态规划 - 地下城游戏(难度⭐⭐⭐)(61)

2024-04-20 08:44

本文主要是介绍【Leetcode每日一题】 动态规划 - 地下城游戏(难度⭐⭐⭐)(61),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 题目解析

题目链接:174. 地下城游戏

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

2.算法原理

一、状态表定义

在解决地下城游戏问题时,我们首先需要对状态进行恰当的定义。一个直观的想法是,从起点开始,到达[i, j]位置时所需的最低初始健康点数。然而,这样的定义会导致状态转移时面临困难,因为当前位置的健康点数会受到后续路径的影响。

为了解决这个问题,我们采用另一种状态定义方式:从[i, j]位置出发,到达终点时所需的最低初始健康点数。这样定义的好处在于,当我们在[i, j]位置时,后续的最佳状态已经确定,从而可以顺利地进行状态转移。

因此,我们定义状态表dp如下:dp[i][j]表示从[i, j]位置出发,到达终点时所需的最低初始健康点数。

二、状态转移过程

在[i, j]位置,玩家有两种选择:向右走或向下走。我们需要根据这两种选择来推导dp[i][j]的值。

  1. 向右走到达下一个位置,然后从该位置继续到达终点。根据状态定义,这要求我们在[i, j]位置的最低健康点数加上当前位置的消耗,应大于等于右边位置的最低健康点数。即:x + dungeon[i][j] >= dp[i][j + 1]。通过移项,我们得到x的一个可能取值:x >= dp[i][j + 1] - dungeon[i][j]。

  2. 向下走到达下一个位置,然后从该位置继续到达终点。同样地,我们要求[i, j]位置的最低健康点数加上当前位置的消耗,应大于等于下边位置的最低健康点数。即:x + dungeon[i][j] >= dp[i + 1][j]。通过移项,我们得到x的另一个可能取值:x >= dp[i + 1][j] - dungeon[i][j]。

为了得到最小的初始健康点数,我们取这两种情况下的最小值作为dp[i][j]的候选值。因此,状态转移方程为:dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。

然而,需要注意的是,如果当前位置的dungeon[i][j]是一个较大的正数,那么dp[i][j]的值可能会变成0或负数,这意味着最低点数会小于1,导致玩家死亡。因此,我们需要对dp[i][j]进行修正,确保其值至少为1。修正后的状态转移方程为:dp[i][j] = max(1, dp[i][j])。

三、初始化

为了正确地进行状态转移,我们需要对dp表进行初始化。一个常用的技巧是在dp表的最前面添加一行和一列辅助节点。这些辅助节点的值需要保证后续填表是正确的。在本题中,我们可以将所有辅助节点的值初始化为无穷大,然后设置dp[m][n - 1] = dp[m - 1][n] = 1,其中m和n分别是地图的行数和列数。

四、填表顺序

根据状态转移方程,我们需要从下往上逐行填写dp表,每行从左往右进行填写。这样的填表顺序可以确保在计算每个位置的dp值时,其右侧和下方的位置已经计算完毕,从而可以利用这些已知值进行状态转移。

五、返回值

最后,根据状态表定义,我们需要返回dp[0][0]的值,即从起点出发到达终点时所需的最低初始健康点数。

3.代码编写

class Solution 
{
public:int calculateMinimumHP(vector<vector<int>>& d) {int m = d.size(), n = d[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));dp[m][n - 1] = dp[m - 1][n] = 1;for(int i = m - 1; i >= 0; i--){for(int j = n - 1; j >= 0; j--){dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - d[i][j];dp[i][j] = max(1, dp[i][j]);}}return dp[0][0];}
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~

这篇关于【Leetcode每日一题】 动态规划 - 地下城游戏(难度⭐⭐⭐)(61)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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需要

SpringBoot实现动态插拔的AOP的完整案例

《SpringBoot实现动态插拔的AOP的完整案例》在现代软件开发中,面向切面编程(AOP)是一种非常重要的技术,能够有效实现日志记录、安全控制、性能监控等横切关注点的分离,在传统的AOP实现中,切... 目录引言一、AOP 概述1.1 什么是 AOP1.2 AOP 的典型应用场景1.3 为什么需要动态插

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求:定时任务扫描,反射调用目标对象,但是,方法的传参不是固定的。方案一:将方法参数存成jsON字

Python开发围棋游戏的实例代码(实现全部功能)

《Python开发围棋游戏的实例代码(实现全部功能)》围棋是一种古老而复杂的策略棋类游戏,起源于中国,已有超过2500年的历史,本文介绍了如何用Python开发一个简单的围棋游戏,实例代码涵盖了游戏的... 目录1. 围棋游戏概述1.1 游戏规则1.2 游戏设计思路2. 环境准备3. 创建棋盘3.1 棋盘类