题目链接：Dungeon Game
The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
┌—————┬—————┬—————┐
|-2(K)| -3 | 3 |
├—————┼—————┼—————┤
| -5 | -10 | 1 |
├—————┼—————┼—————┤
| 10 | 30 |-5(P)|
└—————┴—————┴—————┘
Notes:
- The knight’s health has no upper bound.
- Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
这道题的要求是在一个MxN的地牢中，一个骑士（K）需要从左上角出发到右下角去拯救一个公主（P）。初始时骑士有一个血量，一旦血量为0或者更低，他将立马死去。地牢的一些房间里可能有恶魔的守卫，因此其实可能损失一些血量（负数），而另一些房间是空的（0）或者有魔法药水可以给其实回复血量（正数）。同时，为了尽快拯救公主，骑士只能向下或者向右移动。目的是确定骑士的最小初始健康使其能够拯救公主。注意：骑士血量没有上限，每个房间都可能包含守卫或者魔法药水，即使是在初始房间（左上角）和公主囚禁房间（右下角）。
和Minimum Path Sum类似的题目，不过这个需要确保最小的健康值不能低于1。
-
右下->左上
同样采用动态规划，二维数组dp[i][j]表示骑士在进入房间dungeon[i][j]前的最低血量，以确保其实进入该房间后能存活下来。因此，dp[0][0]就是要求的值。接下来需要从右下向左上依次计算每个dp[i][j]的值。
计算每个dp值的时候，由于到dungeon[i][j]有两个地方dungeon[i+1][j]和dungeon[i][j+1]，当然要选择这两个位置对应dp值小的（min(dungeon[i+1][j], dungeon[i][j+1])），这样才能保证会使dungeon[i][j]更小，即最终会使dungeon[0][0]达到最小。因此对推公式为：
- dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
其中与1取较大值是因为要确保骑士的血量至少为1。
时间复杂度：O(mn)（mn分别为地牢的长宽）
空间复杂度：O(mn)（mn分别为地牢的长宽）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution
{
public:
int calculateMinimumHP(vector<vector<int> > &dungeon)
{
int n = dungeon.size(), m = dungeon[0].size();
vector<vector<int> > dp(n, vector<int>(m, 0));
dp[n - 1][m - 1] = max(1, 1 - dungeon[n - 1][m - 1]);
for(int i = n - 2; i >= 0; -- i)
dp[i][m - 1] = max(1, dp[i + 1][m - 1] - dungeon[i][m - 1]);
for(int j = m - 2; j >= 0; -- j)
dp[n - 1][j] = max(1, dp[n - 1][j + 1] - dungeon[n - 1][j]);
for(int i = n - 2; i >= 0; -- i)
for(int j = m - 2; j >= 0; -- j)
dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
return dp[0][0];
}
};
-
左上->右下
要想从左上到右下，就需要赋予一个初始的血量。至于这个初始血量的选择，可以采用二分的思路，尝试1~INT_MAX范围内的整数。当发现初始血量mid不足以使骑士到达右下角，那么就令下界（l）为mid+1；如果可以到达右下角，那么令上界（u）为mid，以便于找到最低的初始血量。
当然，判断骑士能否到达右下角，用的依旧是dp的思路，只不过需要在骑士血量低于1的时候，标记成INT_MIN，以便于在最后判断骑士能否到达右下角。
时间复杂度：O(mnlog(INT_MAX))（mn分别为地牢的长宽）
空间复杂度：O(mnlog(INT_MAX))（mn分别为地牢的长宽）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution
{
public:
int calculateMinimumHP(vector<vector<int> > &dungeon)
{
int n = dungeon.size(), m = dungeon[0].size();
int l = 1, u = INT_MAX, dead = INT_MIN;
while(l < u)
{
int mid = l + (u - l) / 2;
vector<vector<int>> dp(n + 1, vector<int>(m + 1, dead));
dp[0][1] = dp[1][0] = mid;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
{
int hp = max(dp[i - 1][j], dp[i][j - 1]);
if(hp == dead || hp + dungeon[i - 1][j - 1] < 1)
dp[i][j] = dead;
else
dp[i][j] = hp + dungeon[i - 1][j - 1];
}
if(dp[n][m] < 1)
l = mid + 1;
else
u = mid;
}
return l;
}
};