Best solution I have found with explanations


  • 42
    L

    http://leetcodesolution.blogspot.com/2015/01/leetcode-dungeon-game.html

    seems pretty simple... and easy to understand explanations...

    It is easy to know that at grid P, since " at any point his health point drops to 0 or below, he dies immediately", the remaining health value should be at least 1, that is, initialHealth + dungeon >= 1, we have initialHealth = max(1, 1 - dungeon[i][j]). (Notice, at any grid, the initial health should be at least 1 (for example, test case [1,0,0] require initial health 1 even though it has positive remaining health at grid[0][1] and grid[0][2])
    Similarly, to satisfy the initial health of dungeon[i][j], the initial health of dungeon[i-1][j] (or dungeon[i][j-1]) should be at least initialHealth[i-1][j] + dungeon[i-1][j] = initialHealth[i][j], that is, initialHealth[i][j] = initialHealth[i][j] - dungeon[i-1][j].
    In addition, if grid[i][j] can go both grid[i+1][j] and grid[i][j+1] to P, we should choose a path with less initial health between grid[i+1][j] and grid[i][j+1] since it require less initial health of grid[i][j].
    We can simply code the solution by having the dynamic programming equations.

         int calculateMinimumHP(vector &dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector minInitHealth(m, vector<int>(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)
                {
                    minInitHealth[i][j] = max(1, 1 - dungeon[i][j]);
                }  
                else if (i == m-1)
                {
                    minInitHealth[i][j] = max(1, minInitHealth[i][j+1] - dungeon[i][j]);
                }  
                else if (j == n-1)
                {
                    minInitHealth[i][j] = max(1, minInitHealth[i+1][j] - dungeon[i][j]);
                }  
                else
                {
                    minInitHealth[i][j] = max(1, min(minInitHealth[i+1][j],minInitHealth[i][j+1]) - dungeon[i][j]);
                }  
            }
        }
        
        return  minInitHealth[0][0];
    }

  • 19
    Y

    Very concise and understandable code.

    There is no need to build an extra auxiliary minInitHealth matrix. Just use dungeon to save the DP result from bottom right to top left

    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        
        if(dungeon.size()==0) return 0;
        
        int row=dungeon.size();
        int col=dungeon[0].size();
        
        for(int i=row-1; i>=0; i--) {
            
            for(int j=col-1; j>=0; j--) {
                
                if(i==row-1 && j==col-1) dungeon[i][j]=max(1, 1-dungeon[i][j]);
                else if(i==row-1) dungeon[i][j]=max(1, dungeon[i][j+1]-dungeon[i][j]);
                else if(j==col-1) dungeon[i][j]=max(1, dungeon[i+1][j]-dungeon[i][j]);
                else dungeon[i][j]=max(1, min(dungeon[i+1][j], dungeon[i][j+1])-dungeon[i][j]);
            }
        }
            
        return dungeon[0][0];
    }
    

    Thanks


  • 0
    J

    best solution and explanation.


  • 1

    very terse and clear solution.


  • 0
    L

  • 2
    O

    initialHealth[i][j] = initialHealth[i][j] - dungeon[i-1][j]
    the first "initialHealth[i][j]" should be "initialHealth[i - 1][j]"


Log in to reply
 

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