C++ DP without extra space


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

Log in to reply
 

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