class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
}
};
174. 地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
说明:
骑士的健康点数没有上限。
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2023-09-24 18:32:41
func calculateMinimumHP(dungeon [][]int) int {
n, m := len(dungeon), len(dungeon[0])
dp := make([][]int, n + 1)
for i := 0; i < len(dp); i++ {
dp[i] = make([]int, m + 1)
for j := 0; j < len(dp[i]); j++ {
dp[i][j] = math.MaxInt32
}
}
dp[n][m - 1], dp[n - 1][m] = 1, 1
for i := n - 1; i >= 0; i-- {
for j := m - 1; j >= 0; j-- {
minn := min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(minn - dungeon[i][j], 1)
}
}
return dp[0][0]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
python3 解法, 执行用时: 88 ms, 内存消耗: 16.9 MB, 提交时间: 2023-09-24 18:32:26
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
n, m = len(dungeon), len(dungeon[0])
BIG = 10**9
dp = [[BIG] * (m + 1) for _ in range(n + 1)]
dp[n][m - 1] = dp[n - 1][m] = 1
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
minn = min(dp[i + 1][j], dp[i][j + 1])
dp[i][j] = max(minn - dungeon[i][j], 1)
return dp[0][0]
java 解法, 执行用时: 2 ms, 内存消耗: 42.5 MB, 提交时间: 2023-09-24 18:32:15
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int n = dungeon.length, m = dungeon[0].length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; ++i) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[n][m - 1] = dp[n - 1][m] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = Math.max(minn - dungeon[i][j], 1);
}
}
return dp[0][0];
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 9.1 MB, 提交时间: 2023-09-24 18:31:35
/**
* dp[i][j] 表示从坐标 (i,j) 到终点所需的最小初始值。
* 换句话说，当我们到达坐标 (i,j) 时，如果此时我们的路径和不小于 dp[i][j]，我们就能到达终点。
*/
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int n = dungeon.size(), m = dungeon[0].size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
dp[n][m - 1] = dp[n - 1][m] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
int minn = min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = max(minn - dungeon[i][j], 1);
}
}
return dp[0][0];
}
};