# C++ solution, Dynamic programming O(m*n) time, O(n) space

• ``````class Solution {
public:
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int m = dungeon.size();
int n;
if( m == 0 )
return 0;
else
n = dungeon[0].size();
vector<int> minHP(n, 0);
for( int i = m -1; i >= 0; i-- )
{
for( int j = n-1; j >=0; j-- )
{
if( i == m-1 && j==n-1 )    // bottom-right one
minHP[j] = 1 - dungeon[i][j];
else if( i == m-1 )           // last row
minHP[j] = minHP[j+1] - dungeon[i][j];
else if( j == n-1 )           // last col
minHP[j] = minHP[j] - dungeon[i][j];
else
minHP[j] = min(minHP[j],minHP[j+1]) - dungeon[i][j];    // others
if( minHP[j] <= 0 )    // insure have one
minHP[j] = 1;
}
}
return minHP[0];
}
};``````

• I gave the similar solution as yours in Java, but I used m*n space. I'm just wondering how your one dimension array minHP represents the results. In my version, I use two dimension array minHP[][] and return minHP[0][0] as the final result. What does your one dimension array stands for?

• This post is deleted!

• Because when we compute the m row of HP only use m+1 row of HP,if we have computed the m row of HP,the m+1 row is useless. so we can use only one row to accomplish it

• Yea.. By changing the java like yours, I see what you mean. The minHP is copied from the last row to another until the first, eliminating redundant caching.

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