Dynamic solution c++

• ``````class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.empty())
return 0;
int n = dungeon.size();
int m = dungeon[0].size();

vector<int> dp(m, 0);

//start from bottom line ,right to left
for (int j = m - 1; j >= 0; j--) {
if (j == m - 1)
dp[m - 1] = dungeon[n-1][m - 1] > 0 ? 1 : 1 - dungeon[n-1][m - 1];//bottom right initial
else {
dp[j] = dp[j+1] - dungeon[n - 1][j] > 0 ? dp[j+1] - dungeon[n - 1][j] : 1;//initialbottom line
}
}
for (int i = n - 2; i >= 0;i--) {//from bottom second line to update
for (int j = m - 1; j >= 0; j--) {
if (j == m - 1) {
dp[j] = dp[j] - dungeon[i][j]>0 ? dp[j] - dungeon[i][j] : 1;//when j = m-1, use only dp[j] to update
}
else {
dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j] > 0 ? min(dp[j], dp[j + 1]) - dungeon[i][j] : 1;//use minimum of dp[j] and dp[j+1]to update
}
}
}

return dp[0];
}
};

``````

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