Dungeon Game

This approach uses simple recursion to explore all possible paths from the knight's starting position to the princess. The core idea is to work backward from the destination. We define a function that calculates the minimum health required at a cell (i, j) to guarantee survival until the end. This function recursively calls itself for the next possible cells (down and right) and chooses the path that requires less health.

1. Define a recursive function findMinHealth(row, col) that returns the minimum health needed upon entering cell (row, col).
2. Base Case: If the cell is the princess's room (m-1, n-1), the health h needed must satisfy h + dungeon[m-1][n-1] >= 1. So, the required health is max(1, 1 - dungeon[m-1][n-1]).
3. Boundary Conditions: If row or col goes out of the grid, it's an invalid path. Return a very large value (e.g., Integer.MAX_VALUE) to ensure this path is not chosen.
4. Recursive Step: For any other cell (row, col), the knight can move down or right. The minimum health required for the rest of the journey is the minimum of the health needed for the path starting from (row+1, col) and the path from (row, col+1).
   • minHealthForFuture = min(findMinHealth(row+1, col), findMinHealth(row, col+1))
   • The health h at (row, col) must satisfy h + dungeon[row][col] >= minHealthForFuture. Therefore, the health needed is max(1, minHealthForFuture - dungeon[row][col]).
5. The initial call is findMinHealth(0, 0).

We define a recursive function, say findMinHealth(row, col), which calculates the minimum health required upon entering the cell (row, col) to be able to reach the princess. The function works as follows:

• The base case is the princess's room at (m-1, n-1). To survive this room, the knight's health h must satisfy h + dungeon[m-1][n-1] >= 1. Since health must always be at least 1, the minimum health required upon entering this cell is max(1, 1 - dungeon[m-1][n-1]).

• For any other cell (row, col), the knight can move down to (row+1, col) or right to (row, col+1). He will logically choose the path that requires a lower initial health. The minimum health needed for the subsequent journey is min(findMinHealth(row+1, col), findMinHealth(row, col+1)). Let's call this minHealthForFuture.

• The health h upon entering (row, col) must be sufficient to survive the current room and the rest of the journey. This means h + dungeon[row][col] >= minHealthForFuture. Thus, the health needed at (row, col) is max(1, minHealthForFuture - dungeon[row][col]).

This recursive structure explores all possibilities, but since findMinHealth for the same cell is called multiple times through different paths, it leads to an exponential number of computations.

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // This will likely time out for larger inputs.
        return findMinHealth(dungeon, 0, 0);
    }

    private int findMinHealth(int[][] dungeon, int row, int col) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        if (row >= m || col >= n) {
            return Integer.MAX_VALUE;
        }

        if (row == m - 1 && col == n - 1) {
            return Math.max(1, 1 - dungeon[row][col]);
        }

        int healthFromDown = findMinHealth(dungeon, row + 1, col);
        int healthFromRight = findMinHealth(dungeon, row, col + 1);

        int minHealthForFuture = Math.min(healthFromDown, healthFromRight);
        
        int neededHealth = minHealthForFuture - dungeon[row][col];

        return Math.max(1, neededHealth);
    }
}