Problem Description

The Dungeon Game problem presents a 2D grid, referred to as dungeon, where each cell contains an integer representing the health points gained or lost upon entering that room. The knight starts at the top-left corner of the grid (dungeon[0][0]) and must reach the bottom-right corner (dungeon[m-1][n-1]) to rescue the princess. At each step, the knight can only move either right or down.

The knight must maintain his health points above 0 at all times. If his health drops to 0 or below, he dies immediately. The objective is to determine the minimum initial health points the knight needs so that he can reach the princess alive, regardless of the path taken.

• Each cell's value can be negative (damage), zero (no effect), or positive (healing).
• The knight can only move right or down at each step.
• There is always at least one valid path to the princess.
• The knight’s health must never drop to zero or below at any point.

Thought Process

At first glance, one might consider simulating all possible paths from the start to the end, keeping track of the knight’s health along the way. However, this would be highly inefficient due to the exponential number of possible paths in a grid.

A brute-force approach would involve recursively exploring every possible path and computing the minimum initial health needed for each, but this quickly becomes infeasible for larger grids.

Instead, we shift our perspective: since the goal is to ensure the knight survives all the way to the princess, we can work backwards from the destination. By determining the minimum health required to enter each cell so that the knight can survive to the end, we can efficiently compute the answer using dynamic programming.

Solution Approach

We use dynamic programming to solve this problem efficiently. The key insight is to work backward from the bottom-right cell (the princess’s cell) to the top-left cell, calculating at each step the minimum health required to enter that cell and survive to the end.

1. DP Table Setup:
   • Create a 2D array dp of the same size as dungeon.
   • dp[i][j] represents the minimum health needed to enter cell (i, j) and still reach the princess alive.
2. Base Case:
   • At the princess's cell (m-1, n-1), the knight needs at least 1 health after accounting for the cell's value. So, dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]).
3. Filling the Table:
   • Fill the last row and last column, since from these cells the knight can only move in one direction.
   • For other cells, the knight chooses the path (right or down) that requires less initial health.
   • For each cell, dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).
   • max(1, ...) ensures the knight’s health never drops below 1.
4. Result:
   • The answer is dp[0][0], the minimum initial health needed at the start.

This approach ensures we only compute each subproblem once, making it efficient even for large grids.

Example Walkthrough

Consider the following dungeon:

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

Let’s trace the computation:

• Start at the princess’s cell (2,2): dp[2][2] = max(1, 1 - (-5)) = 6
• Cell (2,1): dp[2][1] = max(1, 6 - 30) = 1 (since 30 is a large positive, only 1 is needed)
• Cell (2,0): dp[2][0] = max(1, 1 - 10) = 1
• Cell (1,2): dp[1][2] = max(1, 6 - 1) = 5
• Cell (1,1): dp[1][1] = max(1, min(1,5) - (-10)) = max(1, 1 + 10) = 11
• Cell (1,0): dp[1][0] = max(1, min(1,11) - (-5)) = max(1, 1 + 5) = 6
• Cell (0,2): dp[0][2] = max(1, 5 - 3) = 2
• Cell (0,1): dp[0][1] = max(1, min(11,2) - (-3)) = max(1, 2 + 3) = 5
• Cell (0,0): dp[0][0] = max(1, min(6,5) - (-2)) = max(1, 5 + 2) = 7

So, the knight needs at least 7 initial health points to survive and rescue the princess.

Time and Space Complexity

Brute-force approach:

• Would explore every possible path from start to finish.
• There are 2^{m+n-2} possible paths for an m x n grid.
• Time complexity: O(2^{m+n}) (exponential).
• Space complexity: O(m+n) for recursion stack.

• We fill each cell of a m x n DP table once.
• Time complexity: O(mn) (linear in the number of cells).
• Space complexity: O(mn) for the DP table (can be optimized to O(n) if only two rows are used at a time).

Summary

The Dungeon Game problem is efficiently solved using a reverse dynamic programming approach. By computing the minimum health required to enter each cell, starting from the princess’s cell and working backward, we ensure the knight always survives the journey. This method avoids redundant recalculations and leverages the grid’s structure for an elegant and optimal solution. The key insight is to focus on the minimum health needed at each step, rather than simulating every possible path.

Code Implementation

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = dp[m - 1][n] = 1

        for i in reversed(range(m)):
            for j in reversed(range(n)):
                min_health = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, min_health)
        return dp[0][0]
      

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int min_health = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, min_health);
            }
        }
        return dp[0][0];
    }
};
      

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int[] row : dp)
            Arrays.fill(row, Integer.MAX_VALUE);
        dp[m][n - 1] = dp[m - 1][n] = 1;

        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int min_health = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, min_health);
            }
        }
        return dp[0][0];
    }
}
      

var calculateMinimumHP = function(dungeon) {
    const m = dungeon.length, n = dungeon[0].length;
    const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(Infinity));
    dp[m][n - 1] = dp[m - 1][n] = 1;

    for (let i = m - 1; i >= 0; --i) {
        for (let j = n - 1; j >= 0; --j) {
            const min_health = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            dp[i][j] = Math.max(1, min_health);
        }
    }
    return dp[0][0];
};