https://leetcode.com/problems/dungeon-game/
[LeetCode]Dungeon Game - 推酷
http://zhuixin8.com/2016/10/02/leetcode-174/
https://discuss.leetcode.com/topic/7633/best-solution-i-have-found-with-explanations
https://xuezhashuati.blogspot.com/2017/05/174-dungeon-game.html
We start from the princess's room and use dynamic programming to solve this problem.
We define health[i][j] to be the minimum health that the prince need to enter room (i, j) such that he can survive through the end.
health[i][j] depends on the its right room and bottom room.
The time complexity is O(mn) and the space complexity is also O(mn).
幸运的是，这个问题可以通过“table-filling”（表格填充）动态规划算法解决，与其他"grid walking"（格子行走）问题类似：
首先，我们应该维护一个2维数组D，与地牢数组的大小相同，其中D[i][j]代表可以保证骑士在进入房间(i,j)之前，探索其余地牢时能够存活下来的最小HP。显然D[0][0]就是我们随后需要的最终答案。因此，对于这个问题，我们需要从右下角到左上角填充表格。
然后，我们来计算离开房间(i,j)时的最小HP。从这一点出发只有两条路径可选：(i + 1, j)和(i, j + 1)。当然我们会选择拥有更小D值的那个房间，换言之，骑士完成剩下的旅途所需的较小HP。因此我们有：
min_HP_on_exit = min(D[i+1][j], D[i][j+1])
http://www.davex.pw/2016/01/21/LeetCode-Dungeon-Game/
X. DP - O(n) space
http://www.cnblogs.com/grandyang/p/4233035.html
X. Bisection
https://leetcode.com/problems/dungeon-game/discuss/52817/Knight-to-Princess-(and-not-reverse-direction)-solution-using-binary-search
Because it is also possible to use binary search on HP for this particular problem. The idea is: for the middle value of the possible range of HP, we use DP to check if this middle value is too high or too low, and then repeat this process and throw half of the HP values that are impossible. The draw back of this problem is that it takes O(log(INT_MAX)MN), and only applies to integer HP values.
https://leetcode.com/problems/dungeon-game/discuss/52899/A-Simple-C%2B%2B-Solution-using-Binary-Search
http://www.fgdsb.com/2015/01/06/harry-potter-game/
DP题，可以从右下角往左上角扫。递推公式如下：
dp[i][j] = max(1, min(dp[i][j+1] - mat[i][j], dp[i+1][j] - mat[i][j]))
G家题讨论： harry potter 走矩阵
假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
http://www.geeksforgeeks.org/minimum-positive-points-to-reach-destination/
Read full article from [LeetCode]Dungeon Game - 推酷
[LeetCode]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.
http://zhuixin8.com/2016/10/02/leetcode-174/
假设骑士位于坐标为(i, j)的位置上，如果我们想要知道从这一点出发到达公主所在的房间所需要的最少血量(记为dp[i][j])的话，与哪些因素有关系呢？因为骑士只能向右或者向下走，因此该值取决于三个方面：
- 骑士从坐标(i+1,j)出发到达公主所在的房间所需要的最少血量，dp[i+1][j]；
- 骑士从坐标(i,j+1)出发到达公主所在的房间所需要的最少血量，dp[i][j+1]；
- 坐标(i,j)所在的房间中包含的补给或威胁对应的数值，dungeon[i][j]。
分析到这里，其实可以看出动态规划转移方程的雏形了，具体描述如下：
其中，表示从向右或者向下的道路中选择所需血量较少的那一条路前进，因为房间中可能有怪物或者补给，所以得到的值需要减去这个房间中补给或怪物对应的数值dungeon[i][j]，又因为骑士的血量不能低于1，因此还需要执行max函数来保证dp[i][j]大于等于1。
然后根据动态规划转移方程从右向左、从下到上依次计算，最后得到的dp[0][0]即为所求。
相信你对这道题目动态规划解法的来龙去脉已经理清楚了。需要注意的是，在写代码的过程中一定要注意边界的检查，不要出现数组越界的情况。
seems pretty simple... and easy to understand explanations...
It is easy to know that at grid P, since " at any point his health point drops to 0 or below, he dies immediately", the remaining health value should be at least 1, that is, initialHealth + dungeon >= 1, we have initialHealth = max(1, 1 - dungeon[i][j]). (Notice, at any grid, the initial health should be at least 1 (for example, test case [1,0,0] require initial health 1 even though it has positive remaining health at grid[0][1] and grid[0][2])
Similarly, to satisfy the initial health of dungeon[i][j], the initial health of dungeon[i-1][j] (or dungeon[i][j-1]) should be at least initialHealth[i-1][j] + dungeon[i-1][j] = initialHealth[i][j], that is, initialHealth[i][j] = initialHealth[i][j] - dungeon[i-1][j].
In addition, if grid[i][j] can go both grid[i+1][j] and grid[i][j+1] to P, we should choose a path with less initial health between grid[i+1][j] and grid[i][j+1] since it require less initial health of grid[i][j].
We can simply code the solution by having the dynamic programming equations.
Similarly, to satisfy the initial health of dungeon[i][j], the initial health of dungeon[i-1][j] (or dungeon[i][j-1]) should be at least initialHealth[i-1][j] + dungeon[i-1][j] = initialHealth[i][j], that is, initialHealth[i][j] = initialHealth[i][j] - dungeon[i-1][j].
In addition, if grid[i][j] can go both grid[i+1][j] and grid[i][j+1] to P, we should choose a path with less initial health between grid[i+1][j] and grid[i][j+1] since it require less initial health of grid[i][j].
We can simply code the solution by having the dynamic programming equations.
int calculateMinimumHP(vector &dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
vector minInitHealth(m, vector<int>(n,0));
for(int i=m-1; i>=0; i--)
{
for (int j=n-1; j>=0; j--)
{
if (i == m-1 && j == n-1)
{
minInitHealth[i][j] = max(1, 1 - dungeon[i][j]);
}
else if (i == m-1)
{
minInitHealth[i][j] = max(1, minInitHealth[i][j+1] - dungeon[i][j]);
}
else if (j == n-1)
{
minInitHealth[i][j] = max(1, minInitHealth[i+1][j] - dungeon[i][j]);
}
else
{
minInitHealth[i][j] = max(1, min(minInitHealth[i+1][j],minInitHealth[i][j+1]) - dungeon[i][j]);
}
}
}
return minInitHealth[0][0];
}We start from the princess's room and use dynamic programming to solve this problem.
We define health[i][j] to be the minimum health that the prince need to enter room (i, j) such that he can survive through the end.
health[i][j] depends on the its right room and bottom room.
The time complexity is O(mn) and the space complexity is also O(mn).
public int calculateMinimumHP(int[][] dungeon) { int m = dungeon.length; int n = dungeon[0].length; int[][] health = new int[m][n]; health[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]); for (int i = m - 2; i >= 0; i--) { health[i][n - 1] = Math.max(1, health[i + 1][n - 1] - dungeon[i][n - 1]); } for (int j = n - 2; j >= 0; j--) { health[m - 1][j] = Math.max(1, health[m - 1][j + 1] - dungeon[m - 1][j]); } for (int i = m - 2; i >= 0; i--) { for (int j = n - 2; j >= 0; j--) { int toRight = Math.max(1, health[i][j + 1] - dungeon[i][j]); int toBottom = Math.max(1, health[i + 1][j] - dungeon[i][j]); health[i][j] = Math.min(toRight, toBottom); } } return health[0][0]; }http://www.cnblogs.com/jcliBlogger/p/4764126.html
Of course, the 2d array can be simplified to a 1d array if we've been clear of how dp is updated (in the above code, dp is updated row by row from the bottom one to the top one and in each row it is updated from right to left). The 1d version is as follows.
3 int calculateMinimumHP(vector<vector<int>>& dungeon) { 4 int m = dungeon.size(), n = dungeon[0].size(); 5 vector<int> dp(n + 1, INT_MAX); dp[n - 1] = 1; // initialization 6 for (int i = m - 1; i >= 0; i--) 7 for (int j = n - 1; j >= 0; j--) 8 dp[j] = max(min(dp[j], dp[j + 1]) - dungeon[i][j], 1); 9 return dp[0];
public int calculateMinimumHP(int[][] dungeon) { int m = dungeon.length; int n = dungeon[0].length; int[][] health = new int[m][n]; health[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1); for (int i = m - 2; i >= 0; i--) { health[i][n - 1] = Math.max(health[i + 1][n - 1] - dungeon[i][n - 1], 1); } for (int j = n - 2; j >= 0; j--) { health[m - 1][j] = Math.max(health[m - 1][j + 1] - dungeon[m - 1][j], 1); } for (int i = m - 2; i >= 0; i--) { for (int j = n - 2; j >= 0; j--) { int down = Math.max(health[i + 1][j] - dungeon[i][j], 1); int right = Math.max(health[i][j + 1] - dungeon[i][j], 1); health[i][j] = Math.min(right, down); } } return health[0][0]; }D[0][0]就是最终答案。 此外，像许多其他"table-filling"问题一样，二维数组D可以用一维滚动数组替代。http://www.cnblogs.com/EdwardLiu/p/4257577.htmlDP题目关键就是两点：1. 维护量； 2. 递归方程因为是从最右下角的格子往前面推，所以dp[i][j]表示的进入某个格子的最小HP是能够保证他走到最右下角的。也是因为有了这个保证，我们选往右还是往下根据dp[i+1][j] < dp[i][j+1] ? 递归方程是dp[i][j] = Math.max(1, - dungeon[i][j] + Math.min(dp[i+1][j], dp[i][j+1])).
http://www.davex.pw/2016/01/21/LeetCode-Dungeon-Game/
一开始，我们应该创建一个和
Dungeon 同样大小的二维数组 Health 。
其中，
Health[i][j] 代表的是该格最小的血量以保证 Knight 在进入 Room(i,j) 之后血量不会低于0.
显然，
Health[0][0] 就是我们要的最终答案——最小初始血量。
因此，这道题我们要倒着做，从
Princess （右下角）到 Knight （左上角）来计算和维护我们的二维数组 Health 。
然后，我们就开始计算离开
Room(i,j) 时所需要的最小血量。
离开的时候，我们有且仅有两条路可以走：
Room(i+1,j) 和 Room(i,j+1) 。
当然，我们会选择使
Health 值最小的房间，也就是说 Knight 完成任务所需要的最小血量。
这样，我们就会有
min_HP_on_exit = min(Health[i+1][j], Health[i][j+1])
现在，
Health[i][j] 就可以从 Dungeon[i][j] 中计算出来。min_HP_on_exit 将会基于以下集中情况：Dungeon[i][j] == 0什么事情都不会发生，骑士将会安然无恙的从该房间离开。离开时的血量将和他进来时的血量一直，即：Health[i][j] = min_HP_on_exitDungeon[i][j] < 0为了使Knight的血量不低于0，在进入Room(i,j)之前，其血量必需大于min_HP_on_exit。那么，最少需要有-Dungeon[i][j]的补偿量，所以我们会有Health[i][j] = min_HP_on_exit - Dungeon[i][j]。Dungeon[i][j] > 0骑士可以最小以min_HP_on_exit - Dungeon[i][j]的血量进入Room[i][j]。但是，这个min_HP_on_exit - Dungeon[i][j]的数值可以小于等于0。那么，在这种情况下，我们必须拿1和这个数值比以确保我们Health[i][j]是正数：Health[i][j] = max(min_HP_on_exit - Dungeon[i][j], 1)
注意到
Dungeon[i][j] > 0 其实还覆盖着其他的两种情况，但是对于任何Dungeon[i][j]我们都可以用同一个等式来计算：
|
|
到了最后，
Health[0][0]就是我们最终的答案。
与此同时，像许多其他
table-filling类型的问题，二维数组也可以被滚动数组所替代。http://www.programcreek.com/2014/03/leetcode-dungeon-game-java/Also, like many other “table-filling” problems, the 2D array D can be replaced with a 1D “rolling” array here.
public int calculateMinimumHP(int[][] dungeon) { int m = dungeon.length; int n = dungeon[0].length; //init dp table int[][] h = new int[m][n]; h[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1); //init last row for (int i = m - 2; i >= 0; i--) { h[i][n - 1] = Math.max(h[i + 1][n - 1] - dungeon[i][n - 1], 1); } //init last column for (int j = n - 2; j >= 0; j--) { h[m - 1][j] = Math.max(h[m - 1][j + 1] - dungeon[m - 1][j], 1); } //calculate dp table for (int i = m - 2; i >= 0; i--) { for (int j = n - 2; j >= 0; j--) { int down = Math.max(h[i + 1][j] - dungeon[i][j], 1); int right = Math.max(h[i][j + 1] - dungeon[i][j], 1); h[i][j] = Math.min(right, down); } } return h[0][0]; } |
http://www.cnblogs.com/grandyang/p/4233035.html
int calculateMinimumHP(vector<vector<int>>& dungeon) { int m = dungeon.size(), n = dungeon[0].size(); vector<int> dp(n + 1, INT_MAX); dp[n - 1] = 1; for (int i = m - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j]); } } return dp[0]; }
https://leetcode.com/problems/dungeon-game/discuss/52785/DFS%2BCache-beat-98.8.-Including-transfer-to-DP-and-space-optimize
X. DFS + cache public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length, col = dungeon[0].length;
int[][] F = new int[2][col];
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i == row - 1 && j == col - 1) F[i % 2][j] = dungeon[i][j] > 0 ? 0 : dungeon[i][j];
else {
int left = i + 1 >= row ? Integer.MIN_VALUE : F[(i + 1) % 2][j];
int right = j + 1 >= col ? Integer.MIN_VALUE : F[i % 2][j + 1];
int cur = dungeon[i][j] + Math.max(left, right);
F[i % 2][j] = cur > 0 ? 0 : cur;
}
}
}
return F[0][0] > 0 ? 1 : -F[0][0] + 1;
} int[][] cache;
public int calculateMinimumHP(int[][] dungeon) {
cache = new int[dungeon.length][dungeon[0].length];
int ret = search(dungeon, 0, 0);
return ret > 0 ? 1 : -ret + 1;
}
private int search(int[][] matrix, int x, int y) {
if (x == matrix.length - 1 && y == matrix[0].length - 1) return matrix[x][y] > 0 ? 0 : matrix[x][y];
if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length) return Integer.MIN_VALUE;
if (cache[x][y] != 0) return cache[x][y] == -1 ? 0 : cache[x][y];
int left = search(matrix, x + 1, y);
int right = search(matrix, x, y + 1);
int cur = matrix[x][y] + Math.max(left, right);
cache[x][y] = cur > 0 ? -1 : cur;
return cur > 0 ? 0 : cur;
}
https://leetcode.com/problems/dungeon-game/discuss/52817/Knight-to-Princess-(and-not-reverse-direction)-solution-using-binary-search
Since most solutions solve it in reverse (which is actually pretty neat), what I cam up with is a front to back (and not back to front) solution that uses binary search to find the smallest HP required to rescue. Running time is O(n^2 log(D)), where D is the maximum value of an integer.
class Solution {
bool canSolve(vector<vector<int>> &dungeon, int guess) {
dungeon[0][0] += guess;
if (dungeon[0][0] <= 0) return false;
for (int i = 1; i < dungeon.size(); ++i) {
dungeon[i][0] += dungeon[i-1][0];
if (dungeon[i][0] <= 0) {
dungeon[i][0] = INT_MIN / 2;
}
}
for (int i = 1; i < dungeon[0].size(); ++i) {
dungeon[0][i] += dungeon[0][i-1];
if (dungeon[0][i] <= 0) {
dungeon[0][i] = INT_MIN / 2;
}
}
for (int i = 1; i < dungeon.size(); ++i) {
for (int j = 1; j < dungeon[0].size(); ++j) {
dungeon[i][j] += std::max(dungeon[i-1][j], dungeon[i][j-1]);
if (dungeon[i][j] <= 0) {
dungeon[i][j] = INT_MIN / 2;
}
}
}
return dungeon.back().back() != INT_MIN / 2;
}
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.empty() || dungeon[0].empty()) return 1;
int lo = 1, hi = INT_MAX;
int guess = hi;
int mid = lo + (hi - lo) / 2;
while (lo != hi) {
auto dcopy = dungeon;
bool cs = canSolve(dcopy, mid);
if (cs) {
guess = mid;
hi = mid;
} else {
lo = mid + 1;
}
mid = lo + (hi - lo) / 2;
}
return guess;
}Because it is also possible to use binary search on HP for this particular problem. The idea is: for the middle value of the possible range of HP, we use DP to check if this middle value is too high or too low, and then repeat this process and throw half of the HP values that are impossible. The draw back of this problem is that it takes O(log(INT_MAX)MN), and only applies to integer HP values.
https://leetcode.com/problems/dungeon-game/discuss/52899/A-Simple-C%2B%2B-Solution-using-Binary-Search
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int N = dungeon.size();
int M = dungeon[0].size();
// just pick a simple path through the dungeon to obtain an upperbound
int lowerbound = 0;
int upperbound = 1;
for (int i = 0; i < M; i++) {
int val = dungeon[0][i];
if (val < 0) upperbound += (-val);
}
for (int i = 0; i < N; i++) {
int val = dungeon[i][M - 1];
if (val < 0) upperbound += (-val);
}
// A number so small impossible to come back alive from
static const int64_t dead = numeric_limits<int64_t>::min() / 3;
// Binary search looking for the smallest starting health which we
// survive from. Invariant we maintain is lowerbound dies and
// upperbound survives
while (lowerbound < upperbound - 1) {
int mid = (upperbound - lowerbound) / 2 + lowerbound;
// create a buffer N + 1 and M + 1 size so we have sentinal values
// padding the first row and column.
auto cur_health = vector<vector<int64_t> >(N + 1);
for (int n = 0; n <= N; n++) {
cur_health[n].resize(M + 1, dead);
}
// Seed in our starting health
cur_health[0][1] = cur_health[1][0] = mid;
for (int n = 1; n <= N; n++) {
for (int m = 1; m <= M; m++) {
cur_health[n][m] = max(cur_health[n-1][m], cur_health[n][m-1]) + dungeon[n-1][m-1];
if (cur_health[n][m] < 1) {
// Once we are dead, ensure we stay dead
cur_health[n][m] = dead;
}
}
}
// If we have positive health at the end we survived!
if (cur_health[N][M] > 0) {
upperbound = mid;
} else {
lowerbound = mid;
}
}
return upperbound;
}
DP题，可以从右下角往左上角扫。递推公式如下：
dp[i][j] = max(1, min(dp[i][j+1] - mat[i][j], dp[i+1][j] - mat[i][j]))
G家题讨论： harry potter 走矩阵
假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
http://www.geeksforgeeks.org/minimum-positive-points-to-reach-destination/
int minInitialPoints(int points[][C]){ // dp[i][j] represents the minimum initial points player // should have so that when starts with cell(i, j) successfully // reaches the destination cell(m-1, n-1) int dp[R][C]; int m = R, n = C; // Base case dp[m-1][n-1] = points[m-1][n-1] > 0? points[m-1][n-1]: abs(points[m-1][n-1]) + 1; // Fill last row and last column as base to fill // entire table for (int i = m-2; i >= 0; i--) dp[i][n-1] = max(dp[i+1][n-1] - points[i][n-1], 1); for (int j = n-2; j >= 0; j--) dp[m-1][j] = max(dp[m-1][j+1] - points[m-1][j], 1); // fill the table in bottom-up fashion for (int i=m-2; i>=0; i--) { for (int j=n-2; j>=0; j--) { int min_points_on_exit = min(dp[i+1][j], dp[i][j+1]); dp[i][j] = max(min_points_on_exit - points[i][j], 1); } } return dp[0][0];}