LeetCode Solutions
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
const int m = dungeon.size();
const int n = dungeon[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[m][n - 1] = 1;
dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; --i)
for (int j = n - 1; j >= 0; --j) {
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = max(dp[i][j], 1);
}
return dp[0][0];
}
};
|
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
final int m = dungeon.length;
final int n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
dp[m][n - 1] = 1;
dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; --i)
for (int j = n - 1; j >= 0; --j) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = Math.max(dp[i][j], 1);
}
return dp[0][0];
}
}
|
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m = len(dungeon)
n = len(dungeon[0])
dp = [math.inf] * (n + 1)
dp[n - 1] = 1
for i in reversed(range(m)):
for j in reversed(range(n)):
dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j]
dp[j] = max(dp[j], 1)
return dp[0]
|
