友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
174. 地下城游戏
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1：
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出：7 解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
示例 2：
输入：dungeon = [[0]] 输出：1
提示：
-
m == dungeon.length -
n == dungeon[i].length -
1 <= m, n <= 200 -
-1000 <= dungeon[i][j] <= 1000
思路分析
动态规划，从终点向起始位置反推。遇到正数就直接加，遇到负数则先看看上一步（因为是反推，上一步就是正着走的下一步）的最大值是正数还是负数，是负数则需要累加，是正数则舍弃，直接从当前位置的负数算起。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-28 22:12:35
*/
public int calculateMinimumHP(int[][] dungeon) {
int rows = dungeon.length;
int cols = dungeon[0].length;
int[][] dp = new int[rows][cols];
dp[rows - 1][cols - 1] = dungeon[rows - 1][cols - 1];
// 最后一列
for (int r = rows - 2; r >= 0; r--) {
if (dungeon[r][cols - 1] > 0) {
dp[r][cols - 1] = dp[r + 1][cols - 1] + dungeon[r][cols - 1];
} else {
if (dp[r + 1][cols - 1] < 0) {
dp[r][cols - 1] = dp[r + 1][cols - 1] + dungeon[r][cols - 1];
} else {
dp[r][cols - 1] = dungeon[r][cols - 1];
}
}
}
// 最后一行
for (int c = cols - 2; c >= 0; c--) {
if (dungeon[rows - 1][c] > 0) {
dp[rows - 1][c] = dp[rows - 1][c + 1] + dungeon[rows - 1][c];
} else {
if (dp[rows - 1][c + 1] < 0) {
dp[rows - 1][c] = dp[rows - 1][c + 1] + dungeon[rows - 1][c];
} else {
dp[rows - 1][c] = dungeon[rows - 1][c];
}
}
}
// 向上汇总
for (int r = rows - 2; r >= 0; r--) {
for (int c = cols - 2; c >= 0; c--) {
int base = Math.max(dp[r][c + 1], dp[r + 1][c]);
if (dungeon[r][c] > 0) {
dp[r][c] = base + dungeon[r][c];
} else {
if (base < 0) {
dp[r][c] = base + dungeon[r][c];
} else {
dp[r][c] = dungeon[r][c];
}
}
}
}
return dp[0][0] > 0 ? 0 : 1 - dp[0][0];
}