My java solution with explanation in detail


  • 21
    Z

    With a health array to store each grid's health, we should get the result at [0][0].

    Now the question become to how to create a health array using dungeon.

    dungeon

    -2,-3,3
    -5,-10,1
    10,30,-5
    

    From the Dungeon grid, we can simply compute health for the [last row][last column].

    Now we get

    ?,?,?
    ?,?,?
    ?,?,6
    

    Now because the knight can only move rightward or downward in each step, we can compute all the health value for last row from right to left using its rightward neighbor. we can also compute all the health value for last column from bottom to up using its downward neighbor.

    ?,?,2
    ?,?,5
    1,1,6
    

    Now, we can compute all the health value using its downward neighbor and rightward neighbor(we use the min value of these 2 health value).

    7,5,2
    6,11,5
    1,1,6
    

    Now we get the answer [0][0], which is 7.

        public int calculateMinimumHP(int[][] dungeon) {
    
            int row = dungeon.length;
            int column = dungeon[0].length;
    
            int[][] tem = new int[row][];
            for (int i = 0; i < tem.length; i++) {
                tem[i] = new int[column];
            }
    
            if (dungeon[row - 1][column - 1] >= 0) {
                tem[row - 1][column - 1] = 1;
            } else {
                tem[row - 1][column - 1] = 1 - dungeon[row - 1][column - 1];
            }
    
            for (int i = row - 2; i >= 0; i--) {
                tem[i][column - 1] = c(dungeon[i][column - 1],
                        tem[i + 1][column - 1]);
            }
    
            for (int j = column - 2; j >= 0; j--) {
                tem[row - 1][j] = c(dungeon[row - 1][j], tem[row - 1][j + 1]);
            }
    
            for (int i = row - 2; i >= 0; i--) {
                for (int j = column - 2; j >= 0; j--) {
                    tem[i][j] = Math.min(c(dungeon[i][j], tem[i + 1][j]),
                            c(dungeon[i][j], tem[i][j + 1]));
                }
            }
    
            return tem[0][0];
        }
    
        private int c(int value, int preResult) {
            if (value == 0)
                return preResult;
    
            if (value > 0) {
                if (value >= preResult)
                    return 1;
                return preResult - value;
            }
    
            return preResult - value;
        }
    }

  • 8
    C

    The explanation is in detail. But it seems there is room to improve the code.

    Dp state equation:
    dp[i][j] - min health at this position so that the knight can survive at bottom-right
    
    Dp State Transition Equation:
    Dp[i][j] = max(1,min(dp[i+1][j],dp[i][j+1]) - grid[i][j]);
    

Log in to reply
 

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