C DP solution in 3ms


  • 0
    D
    int calculateMinimumHP(int** dungeon, int dungeonRowSize, int dungeonColSize) {
        for(int i=dungeonRowSize-1;i>=0;i--){
            for(int j=dungeonColSize-1;j>=0;j--){
                if(i==dungeonRowSize-1&&j==dungeonColSize-1){
                    continue;
                }  
                else if(i==dungeonRowSize-1){
                    if(dungeon[i][j+1]<0){
                        dungeon[i][j]+=dungeon[i][j+1];
                    }
                }
                else if(j==dungeonColSize-1){
                    if(dungeon[i+1][j]<0){
                        dungeon[i][j]+=dungeon[i+1][j];
                    }
                }
                else{
                    int max=dungeon[i+1][j]>=dungeon[i][j+1]?dungeon[i+1][j]:dungeon[i][j+1];
                    if(max<0){
                        dungeon[i][j]+=max;
                    }
                }
            }
        }
        return dungeon[0][0]>=0?1:1-dungeon[0][0];
    }
    

Log in to reply
 

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