Dungeon Game

XXX. Dungeon Game

Dynamic Programming

Problem Statement:

The knight is placed in the top-left corner of a dungeon, and his goal is to reach the bottom-right corner. Each cell contains an integer, which could either increase (positive) or decrease (negative) the knight's health. The knight must maintain a minimum health of 1 at all times.

Example:

Input:

            dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
        

Output:

7

Explanation: To reach the goal with at least 1 health at every step, the knight needs an initial health of 7.

Approach:

1. Start from the bottom-right corner and work backwards, calculating the minimum health required to proceed to the next cell.
2. At each cell, calculate the health needed to survive using the minimum of the health needed from the right or below.
3. Ensure the knight's health at any point is at least 1.
4. The value at the top-left corner gives the minimum health required.

Algorithm Intuition:

The problem is solved in reverse to ensure that the knight has enough health to survive the dungeon. By working backwards, we avoid overestimating the health requirements for cells that are less critical. Dynamic programming ensures we compute the solution efficiently by reusing previously calculated values.

Complexity:

Time Complexity: O(m × n), where m and n are the dimensions of the dungeon.
Space Complexity: O(1), as the solution modifies the input array in place.

Java Implementation:

public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    
    // Start from the bottom-right corner of the dungeon
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int curr = dungeon[i][j];
            
            // Base case: bottom-right corner
            if (i == m - 1 && j == n - 1) 
                dungeon[i][j] = Math.max(1, 1 - curr);
            
            // Last row: Can only move right
            else if (i == m - 1) 
                dungeon[i][j] = Math.max(1, dungeon[i][j + 1] - curr);
            
            // Last column: Can only move down
            else if (j == n - 1) 
                dungeon[i][j] = Math.max(1, dungeon[i + 1][j] - curr);
            
            // General case: Take minimum health needed from right or below
            else {
                dungeon[i][j] = Math.min(dungeon[i][j + 1] - curr, dungeon[i + 1][j] - curr);
                dungeon[i][j] = Math.max(1, dungeon[i][j]); // Ensure at least 1 health
            }
        }  
    }
    
    // Return the minimum health required at the start
    return dungeon[0][0];
}