C# solution with explanation


  • 1
    G
    public class Solution {
        public int CalculateMinimumHP(int[,] dungeon) {
            int rows = dungeon.GetLength(0);
            int cols = dungeon.GetLength(1);
            
            // save partial solutions in a matrix
            int[,] solutions = new int[rows, cols];
            
            // start with last room in the dungeon and ask the following question:
            // what would the minimum health of the Knight need to be so he can survive the last room?
            // Answer: if the room has a devil (negative value) than his health needs to be at least 1 above
            // the devil's strength. Otherwise (room is empty or has a magic orb) his health only needs to be equal to 1
            // Therefore, we can set his health to the max value between 1 and 1 - dungeon[rows - 1, cols - 1]
            int bottomRow = rows - 1;
            int rightCol = cols - 1;
            solutions[bottomRow, rightCol] = Math.Max(1, 1 - dungeon[bottomRow, rightCol]);
            
            // now that we know the Knight's minimal health required in the last room, we can compute his minimal health
            // in other rooms. For each room he enters, he needs to be strong enough to survie that room AND meet the minimum
            // health required in the next room immediately after that. Since there are two rooms immediately after (except
            // for when his is at the borders), we compute both of those health values and keep the smaller one (because we want the 
            // minumum health required)
            
            // first, we take care of the borders (bottom row and right column)
            
            // right column: traverse the rooms from the bottom to the top and make sure the Knight is strong enough to survive the room
            // AND arrive at the next room (on its bottom side) with a health greater than or equal to solutions[i + 1, rightCol]
            for (int i = bottomRow - 1; i >= 0; i--) {
                solutions[i, rightCol] = Math.Max(1, solutions[i + 1, rightCol] - dungeon[i, rightCol]);
            }
            
            // bottom row: traverse the rooms from right to left and make sure the Knight is strong enough to survive the room AND arrive
            // at the next room (on its right side) with a health greater than or equal to solutions[bottomRow, j + 1]
            for (int j = rightCol - 1; j >= 0; j--) {
                solutions[bottomRow, j] = Math.Max(1, solutions[bottomRow, j + 1] - dungeon[bottomRow, j]);
            }
            
            // now, take care of the inner dungeon. Each room has now two neighboring rooms (to the right and down), so we need
            // to compute the minimum health with respect to each of them. We then take the minimum value.
            for (int i = bottomRow - 1; i >= 0; i--) {
                for (int j = rightCol - 1; j >= 0; j--) {
                    
                    //compute min health to survive this room AND room to the right
                    int minRight = Math.Max(1, solutions[i, j + 1] - dungeon[i, j]);
                    
                    //compute min health to survie this room AND room down to the bottom
                    int minDown = Math.Max(1, solutions[i + 1, j] - dungeon[i, j]);
                    
                    //take min of the two
                    solutions[i, j] = Math.Min(minRight, minDown);
                }
            }
            
            // our solution is the minimal health the Knight needs to have in the very first room (0,0)
            return solutions[0, 0];
        }
    }
    

Log in to reply
 

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