# Share my c++ DP solution with explanation

• ###dp[i][j] means start from point (i,j) end at point (n-1,m-1) need at least dp[i][j] health.###
dp[i][j] = min( max( dp[i+1][j] - dungeon[i][j], 1),
max( dp[i][j+1] - dungeon[i][j], 1) );

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

return dp[0][0];
}
};``````

• Came up with basically the same solution. Why is the runtime complexity O(n^2)?

``````class Solution {
public:
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int widthMinusOne = dungeon.size()-1;
int heightMinusOne = dungeon[0].size()-1;
int j, hpNeededLater, hpNeeded;
bool bottomFlag, rightEdgeFlag;
for (int i = widthMinusOne; 0 <= i; i--){
rightEdgeFlag = i == widthMinusOne ? true : false;
for (j = heightMinusOne; 0 <= j; j--){
bottomFlag = j == heightMinusOne ? true : false;
if (bottomFlag && rightEdgeFlag)
hpNeededLater = 0;
else if (bottomFlag)
hpNeededLater = dungeon[i+1][j];
else if (rightEdgeFlag)
hpNeededLater = dungeon[i][j+1];
else
hpNeededLater = min(dungeon[i+1][j], dungeon[i][j+1]);
hpNeeded = hpNeededLater - dungeon[i][j];
dungeon[i][j] = hpNeeded < 0 ? 0 : hpNeeded;
}
}
return dungeon[0][0]+1;
}
};``````

• sorry,it's O(n*m).

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