class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.size() == 0 || dungeon[0].size() == 0) {
return 1;
}
int n = dungeon.size();
int m = dungeon[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
for(int i = n - 1; i >= 0; i--) {
for(int j = m - 1; j >= 0; j--) {
if ( i == n - 1 && j == m - 1) {
dp[i][j] = max(1, 1 - dungeon[i][j]);
}
else if (i == n - 1) {
dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j]);
}
else if (j == m - 1) {
dp[i][j] = max(1, dp[i + 1][j] - dungeon[i][j]);
}
else
{
dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]));
}
}
}
return dp[0][0];
}
};
