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


  • 0
    A
    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];
        }
    };

  • 0
    R

    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?


  • 0
    A
    This post is deleted!

  • 0
    A

    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


  • 0
    R

    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.


Log in to reply
 

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