Sharing my 16ms C++ solution


  • 0
    T
    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            int m = dungeon.size();
            int n = dungeon[0].size();
            vector<vector<int>> rDP;
            rDP.resize(m);
            int i, j;
            for(i=0; i<m; i++)
                rDP[i].resize(n);
                
            rDP[m-1][n-1] = 1-dungeon[m-1][n-1];
            if(rDP[m-1][n-1] < 1)
                rDP[m-1][n-1] = 1;
                
            
            if(m>=2)
            {
                for(i=m-2; i>=0; i--)
                {
                    rDP[i][n-1] = rDP[i+1][n-1] - dungeon[i][n-1];
                    if(rDP[i][n-1] < 1)
                        rDP[i][n-1] = 1;
                }
            }
            
            if(n>=2)
            {
                for(j=n-2; j>=0; j--)
                {
                    rDP[m-1][j] = rDP[m-1][j+1] - dungeon[m-1][j];
                    if(rDP[m-1][j] < 1)
                        rDP[m-1][j] = 1;
                }
            }
            
            if(m>=2 && n>=2)
            {
                for(i=m-2; i>=0; i--)
                    for(j=n-2; j>=0; j--)
                    {
                        rDP[i][j] = min(rDP[i+1][j], rDP[i][j+1]) - dungeon[i][j];
                        if(rDP[i][j] < 1)
                            rDP[i][j] = 1;
                    }
            }
            return rDP[0][0];
        }
    };

Log in to reply
 

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