174. Dungeon Game
魔物抓住了公主，並將她囚禁在地牢的右下角。這個地牢由 m x n 個房間組成，排列成一個 2D 網格。英勇的騎士最初位於左上角的房間，必須一路戰鬥穿過地牢去拯救公主。
騎士有一個初始生命值，用一個正整數表示。如果他的生命值在任何時候降到 0 或以下，他會立即死亡。
一些房間由魔物看守（用負整數表示），因此騎士進入這些房間時會失去生命值；其他房間要麼是空的（用 0 表示），要麼包含能增加騎士生命值的魔法球（用正整數表示）。
為了盡快到達公主，騎士決定每一步只能向右或向下移動。
返回騎士為了拯救公主所需的最小初始生命值。
注意，任何房間都可能包含威脅或增益，包括騎士進入的第一個房間和囚禁公主的右下角房間。
範例 ：
輸入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
輸出：7
解釋：如果騎士按照最佳路徑：右 -> 右 -> 下 -> 下，他的初始生命值必須至少為 7。
Python
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
if not dungeon or not dungeon[0]:
return 0
m, n = len(dungeon), len(dungeon[0])
dp = [[0] * n for _ in range(m)]
# Start from the bottom-right corner
dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
# Fill the last row
for i in range(n - 2, -1, -1):
dp[-1][i] = max(1, dp[-1][i + 1] - dungeon[-1][i])
# Fill the last column
for i in range(m - 2, -1, -1):
dp[i][-1] = max(1, dp[i + 1][-1] - dungeon[i][-1])
# Fill the rest of the dp table
for i in range(m - 2, -1, -1):
for j in range(n - 2, -1, -1):
min_health_on_exit = min(dp[i + 1][j], dp[i][j + 1])
dp[i][j] = max(1, min_health_on_exit - dungeon[i][j])
return dp[0][0]
17.74MB, 61ms
C++
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
// Start from the bottom-right corner
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]);
// Fill the last row
for (int i = n - 2; i >= 0; --i) {
dp[m-1][i] = max(1, dp[m-1][i + 1] - dungeon[m-1][i]);
}
// Fill the last column
for (int i = m - 2; i >= 0; --i) {
dp[i][n-1] = max(1, dp[i + 1][n-1] - dungeon[i][n-1]);
}
// Fill the rest of the dp table
for (int i = m - 2; i >= 0; --i) {
for (int j = n - 2; j >= 0; --j) {
int min_health_on_exit = min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = max(1, min_health_on_exit - dungeon[i][j]);
}
}
return dp[0][0];
}
};
11.40MB, 4ms
Javascript
/**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function(dungeon) {
const m = dungeon.length;
const n = dungeon[0].length;
const dp = Array.from({ length: m }, () => Array(n).fill(0));
// Start from the bottom-right corner
dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);
// Fill the last row
for (let i = n - 2; i >= 0; --i) {
dp[m - 1][i] = Math.max(1, dp[m - 1][i + 1] - dungeon[m - 1][i]);
}
// Fill the last column
for (let i = m - 2; i >= 0; --i) {
dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
}
// Fill the rest of the dp table
for (let i = m - 2; i >= 0; --i) {
for (let j = n - 2; j >= 0; --j) {
const minHealthOnExit = Math.min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = Math.max(1, minHealthOnExit - dungeon[i][j]);
}
}
return dp[0][0];
};
50.55MB, 61ms
