题目描述:

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.

img

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.

使用二分搜索+DP. 单纯的二维DP是不行的, 因为这道题要求从起点到终点的路径中每个格子的值都不能小于1. 有可能出现终点时生命值大于0但是每一条路径实际上都无法抵达.

但是我们可以使用DP来判断一个特定初始生命值的knight能否救到princess. 然后在外层使用二分搜索来找到最小的初始生命值. 虽然可以用0~INT_MAX作为搜索范围, 但是先找出初始生命值为0时每一条路径中出现的最小的生命值可以大大缩小这个范围, 实际上如果初始生命值为0时, 所有的格子中生命值都是大于1的, 可以直接返回1; 否则搜索范围的最大值就是最小生命值的绝对值加1.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		if (dungeon.empty()) return 0;
		if (dungeon[0].empty()) return 0;
		int tmp = minInPath(dungeon);
		if(tmp > 0) return 1;
		int left = 0, right = -tmp + 1, mid = (right + left) / 2;
		while (left < right) {
			int h = canArrive(dungeon, mid);
			if(h == 1){
			    break;
			}
		    else if (h < 1) {
				left = mid + 1;
			}
			else {
				right = mid;
			}
			mid = (right + left) / 2;
		}
		return mid ? mid : 1;
	}

	int canArrive(vector<vector<int>>& dungeon, int target) {
		int row = dungeon.size(), col = dungeon[0].size();
		vector<vector<int>> dp(row, vector<int>(col, 0));
		dp[0][0] = target + dungeon[0][0];
		for (int i = 1; i < col; i++) {
			if (dp[0][i - 1] > 0) dp[0][i] = dp[0][i - 1] + dungeon[0][i];
		}
		for (int i = 1; i < row; i++) {
			if (dp[i - 1][0] > 0) dp[i][0] = dp[i - 1][0] + dungeon[i][0];
		}
		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if(dp[i - 1][j] > 0 || dp[i][j - 1] > 0)
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dungeon[i][j];
			}
		}
		return dp[row - 1][col - 1];
	}
	
	int minInPath(vector<vector<int>>& dungeon){
	    int row = dungeon.size(), col = dungeon[0].size(), minInPath = INT_MAX;
		vector<vector<int>> dp(row, vector<int>(col, 0));
		dp[0][0] = dungeon[0][0];
		minInPath = min(minInPath, dp[0][0]);
		for (int i = 1; i < col; i++) {
			dp[0][i] = dp[0][i - 1] + dungeon[0][i];
			minInPath = min(minInPath, dp[0][i]);
		}
		for (int i = 1; i < row; i++) {
			dp[i][0] = dp[i - 1][0] + dungeon[i][0];
			minInPath = min(minInPath, dp[i][0]);
		}
		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dungeon[i][j];
				minInPath = min(minInPath, dp[i][j]);
			}
		}
		return minInPath;
	}
};