# 6 lines, 16 ms, C++, O(mn) Time, O(n) Space,

• ``````struct Solution {
int calculateMinimumHP(vector<vector<int>>& d) {
vector<int> dp(d.size() + 1, INT_MAX);
dp[d.size() - 1] = 1;
for (int i = d[0].size() - 1; i >= 0; --i)
for (int j = d.size() - 1; j >= 0; --j)
dp[j] = max(1, min(dp[j + 1], dp[j]) - d[j][i]);
return dp[0];
}
};``````

• Great solution!
I solved this problem with binary search, but it's too slow.

• why do you want to assign 1 when you get a negative value..?

• If at any point the health is <= 0, the soldier dies. So, the minimum possible value for minimum health at any given position is 1. Thus, when we get a negative value for the minimum health at a grid position, we just assign it 1.

• Alternatively last row first, bottom up

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.