Share DP Solution from "Bottom right corner" to "Upper left corner"


  • 0
    N

    Let A[i][j] denotes the least HP when the knight reached dungeon[i][j].

    1. Calculate the least HP at the bottom right corner, dungeon[row-1][col-1]:

    If dungeon[row-1][col-1] > 0, A[i][j] = 1;    // the last room contains supplies
    else A[i][j] = 1 - dungeon[row-1][col-1];     // the last room is guarded by demons
    
    1. Calculate the least HP when the knight in the last column bottom-up;
    2. Calculate the least HP when the knight in the last row from right to left;
    3. Calculate the least HP when the knight in other areas from bottom-right to upper-left.

    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        int row = dungeon.size();
        int col = dungeon[0].size();
        int A[row][col];
        
        // 1. when the knight reached the bottom right corner
        A[row-1][col-1] = (dungeon[row-1][col-1] > 0) ? 1 : (1 - dungeon[row-1][col-1]);
        
        // 2. in the last column, bottom-up;
        for(int i = row - 2; i >= 0; --i) {
            int aboveValue = A[i+1][col-1] - dungeon[i][col-1];
            A[i][col-1]  = aboveValue > 0 ? aboveValue : 1;
        }
        
        // 3. in the last row, from right to left
        for(int j = col - 2; j >= 0; --j) {
            int leftValue = A[row-1][j+1] - dungeon[row-1][j];
            A[row-1][j]  = leftValue > 0 ? leftValue : 1;
        }
        
        // 4. in other areas, from bottom-right to upper-left
        for(int i = row - 2; i >=0; --i) {
            for(int j = col - 2; j >= 0; --j) {
                int rightValue = (A[i][j+1]-dungeon[i][j] > 0) ? A[i][j+1]-dungeon[i][j] : 1;
                int belowValue = (A[i+1][j]-dungeon[i][j] > 0) ? A[i+1][j]-dungeon[i][j] : 1;
                A[i][j] = min(rightValue, belowValue);
            }
        }
        return A[0][0];
    }

Log in to reply
 

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