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

avatar
作者
猴君
阅读量:0

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

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

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

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

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!