Problem Overview

The Dungeon Game is a classic dynamic programming problem that tests your ability to plan backward from a goal.

You are given a 2D grid dungeon where each cell contains an integer representing the health impact on a knight:

• A negative value means the knight loses that much health.
• A positive value means the knight gains that much health.
• A zero means no change.

The knight starts at the top-left cell (0,0) and must reach the bottom-right cell (m−1,n−1), where the princess is trapped. The knight can only move right or down.

The goal is to determine the minimum initial health the knight needs so that he can rescue the princess without his health ever dropping to zero or below at any point in the journey.

Example 1:

Input: dungeon = [[-2,-3,3],
                  [-5,-10,1],
                  [10,30,-5]]
Output: 7

Explanation:

• The knight starts with at least 7 health.
• Path: Right → Right → Down → Down.
• His health never drops below 1 throughout the journey.

---

Intuition and Approach

The problem might seem like a pathfinding problem at first, but a forward approach (from start to end) is tricky because we don’t know the minimum health required at each step until we know what lies ahead.
Therefore, we approach it backward, from the princess’s cell to the starting cell.

We use dynamic programming (DP) to compute the minimum health required to reach the goal safely.
Let dp[i][j] represent the minimum health needed when entering cell (i, j) so that the knight can reach the princess without dying.

We compute this value starting from the bottom-right corner:

• For each cell (i, j), we need enough health to survive that cell and continue safely to the next cell (either right or down).
• Therefore: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
  • min(dp[i+1][j], dp[i][j+1]) chooses the less costly path.
  • Subtract dungeon[i][j] because that cell either hurts or heals the knight.
  • The knight’s health must always be at least 1, hence max(1, ...).

We start from the bottom-right cell (princess’s location):

dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])

Then, we fill the table backward (right to left, bottom to top).

---

Step-by-Step Algorithm

1. Let m = number of rows, n = number of columns.
2. Create a 2D array dp[m][n].
3. Initialize the bottom-right cell: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
4. Fill the last row (can only move right): dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
5. Fill the last column (can only move down): dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
6. Fill the rest of the grid backward using the main relation: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
7. The answer is dp[0][0], representing the minimum health required to start.

---

Java Code Implementation

public class DungeonGame {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        
        int[][] dp = new int[m][n];
        
        // Base case: princess's cell
        dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);
        
        // Fill last row
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }
        
        // Fill last column
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        
        // Fill the rest of the table
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minNextStep = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(1, minNextStep - dungeon[i][j]);
            }
        }
        
        return dp[0][0];
    }
}

---

Complexity Analysis

• Time Complexity: O(m * n)
  Each cell is computed once, and we only look at its right and down neighbors.
• Space Complexity: O(m * n)
  We use a 2D DP array of the same size as the input grid.
  This can be optimized to O(n) if we only store the current and next row.

---

Alternative Approach (Space Optimization)

Instead of using a full 2D DP array, we can optimize space using a 1D array since each cell depends only on its right and bottom cells.