C++ a few lines, DP in-place


  • 0
    A
    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            int M = dungeon.size(), N = dungeon[0].size();
            dungeon[M-1][N-1] = 1 - min(0, dungeon[M-1][N-1]);
            for (int i = M-2; i >= 0; --i) dungeon[i][N-1] = max(1, dungeon[i+1][N-1] - dungeon[i][N-1]);
            for (int j = N-2; j >= 0; --j) dungeon[M-1][j] = max(1, dungeon[M-1][j+1] - dungeon[M-1][j]);
            for (int i = M-2; i >= 0; --i)
                for (int j = N-2; j >= 0; --j)
                    dungeon[i][j] = max(1, min(dungeon[i][j+1], dungeon[i+1][j]) - dungeon[i][j]);
            return dungeon[0][0];
        }
    };
    

Log in to reply
 

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