Three different solutions in C all accepted as best, well-explained


  • 0

    Before we hit the road, let's make it clear that we are about to do:

    • use the minimal health for each room to finally find out the possible minimal health at the top-left start room.
    • If minimal health in the room is bigger than 1, we are to reset it to 1 for global minimal -> the minimal top-left health.

    DP Equation: mins[i][j] = MAX(1, MIN(mins[i+1][j], mins[i][j+1])-dungeon[i][j]);


    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    #define MIN(a, b) ((a) < (b) ? (a) : (b))
    //AC - 8ms;
    int calculateMinimumHP(int** dungeon, int rSize, int cSize)
    {
        int** mins = (int**)malloc(sizeof(int*)*rSize);
        for(int i = 0; i < rSize; i++)
        {
            mins[i] = (int*)malloc(sizeof(int)*cSize);
            memset(mins[i], 0, sizeof(int)*cSize);
        }
        for(int i = rSize-1; i >= 0; i--)
            for(int j = cSize-1; j >= 0; j--)
            {
                if(i==rSize-1 && j==cSize-1)
                    mins[i][j] = MAX(1, 1-dungeon[i][j]);
                else if(i == rSize-1)
                    mins[i][j] = MAX(1, mins[i][j+1]-dungeon[i][j]);
                else if(j == cSize-1)
                    mins[i][j] = MAX(1, mins[i+1][j]-dungeon[i][j]);
                else
                    mins[i][j] = MAX(1, MIN(mins[i+1][j], mins[i][j+1])-dungeon[i][j]);
            }
        return mins[0][0];
    }
    

    //AC - 8ms - reduce the different conditions by adding an edge;
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    #define MIN(a, b) ((a) < (b) ? (a) : (b))
    int calculateMinimumHP(int** dungeon, int rSize, int cSize)
    {
        int** mins = (int**)malloc(sizeof(int*)*(rSize+1));
        for(int i = 0; i <=rSize; i++)
        {
            mins[i] = (int*)malloc(sizeof(int)*(cSize+1));
            memset(mins[i], 0, sizeof(int)*cSize);
        }
        for(int i = 0; i <= rSize; i++)
            mins[i][cSize] = INT_MAX;
        for(int i = 0; i <= cSize; i++)
            mins[rSize][i] = INT_MAX;
        mins[rSize-1][cSize] = 1;
        mins[rSize][cSize-1] = 1;
        for(int i = rSize-1; i >= 0; i--)
            for(int j = cSize-1; j >= 0; j--)
                mins[i][j] = MAX(1, MIN(mins[i+1][j], mins[i][j+1])-dungeon[i][j]);
        return mins[0][0];
    }
    

    //AC - 8ms;
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    #define MIN(a, b) ((a) < (b) ? (a) : (b))
    int calculateMinimumHP(int** dungeon, int rSize, int cSize)
    {
        int *mins = (int*)malloc(sizeof(int)*(cSize+1));
        for(int i = 0; i <= cSize; i++)
            mins[i] = INT_MAX;
        mins[cSize-1] = 1;
        for(int i = rSize-1; i >= 0; i--)
            for(int j = cSize-1; j >= 0; j--)
                mins[j] = MAX(1, MIN(mins[j], mins[j+1])-dungeon[i][j]);
        return mins[0];
    }

Log in to reply
 

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