174. 地下城游戏https://leetcode.cn/problems/dungeon-game/description/
恶魔们抓住了公主并将她关在了地下城dungeon的右下角。地下城是由m x n个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至0或以下,他会立即死亡。有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。为了尽快解救公主,骑士决定每次只向右或向下移动一步。返回确保骑士能够拯救到公主所需的最低初始健康点数。注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
- 输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]],输出:7,解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为7。
- 输入: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