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

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

时间:2024-06-07 19:32:02浏览次数:26  
标签:dungeon 右下角 位置 初始 点数 健康 地下城 dp

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

标签:dungeon,右下角,位置,初始,点数,健康,地下城,dp
From: https://blog.csdn.net/xiang_bolin/article/details/139533349

相关文章

  • c++ 静态成员的初始化 友元模板
     来自:https://www.cnblogs.com/fre2technic/archive/2011/03/25/1995044.html 我们定义如下类://A.hclass A{private:    static const int m = 5;    static int n;    static vector<int> buf;};其中包含三个私有的静态类成员,C++规定const静态......
  • 浮点数
    十进制小数与二进制数的转换十进制整数转换为二进制整数十进制整数转换为二进制整数采用"除2取余,逆序排列"法。具体做法是:用2去除十进制整数,可以得到一个商和余数;再用2去除商,又会得到一个商和余数,如此进行,直到商为零时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的......
  • 【SpringBoot + Vue 尚庭公寓实战】项目初始化准备(二)
    尚庭公寓SpringBoot+Vue项目实战】项目初始化准备(二)文章目录尚庭公寓SpringBoot+Vue项目实战】项目初始化准备(二)1、导入数据库2、创建工程3、项目初始配置3.1、SpringBoot依赖配置3.2、创建application.yml文件3.3、创建SpringBoot启动类4、MyBatisPlus配置4.1......
  • c++类中初始化列表的优点以及顺序问题
    1.使用初始化列表的好处效率:使用初始化列表可以避免不必要的拷贝操作,直接在对象构造时初始化成员变量,提高代码的执行效率。(因为变量的初始化分为初始化阶段和赋值阶段,在{}里面初始化属于赋值阶段)常量成员初始化:可以在初始化列表中对常量成员或引用的对象进行初始化,且只能在初......
  • 初始BootStrap
    官方文档https://v3.bootcss.com/<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Title</title><!--开发版本--><linkrel="stylesheet"href="stati......
  • 初始化容器——initContainers
    转自:https://blog.csdn.net/qq_47261578/article/details/119646847 [root@k8s-master~]#viminit-pod.yaml[root@k8s-master~]#catinit-pod.yamlapiVersion:v1kind:Podmetadata: name:myapp-pod labels:   app:myapp-podspec: containers:   -name:m......
  • js知识点之浮点数精度问题
    浮点数精度问题浮点数精度常见问题在JavaScript中整数和浮点数都属于number数据类型,所有数字都是以64位浮点数形式储存,即便整数也是如此。所以我们在打印1.00这样的浮点数的结果是1而非1.00。在一些特殊的数值表示中,例如金额,这样看上去有点别扭,但是至少值是......
  • Linux 安装了MySQL 8.0后 如何修改初始密码
    1.grep‘temporarypassword’ /var/log/mysqld.log #查看初始临时密码2.systemctlstartmysqld #启动mysql3.mysqladmin-uroot-ppassword‘xxx’ #这里的xxx一般是大写字母加小写字母,数字和字符组成一共12-13个左右就可以修改4.这里的Enterpassword......
  • 自定义FlutterFragment的初始化路由没有生效
    问题:在自定义FlutterFragment的configureFlutterEngine方法中初始化页面路由发现一直是'/'原因:当configureFlutterEngine方法被调用时,Flutter已经完成了初始化并设置了默认的初始路由(通常是'/')。在Android项目中,FlutterFragment在onAttach方法中创建FlutterEngine。在......
  • 浮点数二分查找的实现
            这是C++算法基础-基础算法专栏的第六篇文章,专栏详情请见此处。引入    上次我们学习了整数二分查找的实现,这次我们要学习浮点数二分查找的实现。定义        浮点数二分查找与整数二分查找的定义都是大致相同的,如果想了解具体内容,可以移......