LeetCode 174 - Dungeon Game - 题解/Solution

https://leetcode.com/problems/dungeon-game/

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
/**
* 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.
*
* @author dongyuxi
*
*/
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
if (null == dungeon || 0 == dungeon.length) {
return 0;
}

int row = dungeon.length;
int col = dungeon[0].length;
int[][] dp = new int[row][col];
dp[row - 1][col - 1] = Math.max(0 - dungeon[row - 1][col - 1], 0);
for (int i = row - 2; i >= 0; i--) {
dp[i][col - 1] = Math.max(dp[i + 1][col - 1] - dungeon[i][col - 1], 0);
}
for (int i = col - 2; i >= 0; i--) {
dp[row - 1][i] = Math.max(dp[row - 1][i + 1] - dungeon[row - 1][i], 0);
}
for (int i = row - 2; i >= 0; i--) {
for (int j = col - 2; j >= 0; j--) {
dp[i][j] = Math.max(Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j], 0);
}
}

return dp[0][0] + 1;
}
}


支付宝 微信
文章目录