classic 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.