# Dungeon Game
**Difficulty:** HARD
[External](https://leetcode.com/problems/dungeon-game)
Canonical: https://scaleengineer.com/dsa/problems/dungeon-game
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
The demons had captured the princess and imprisoned her in **the bottom-right corner** of a `dungeon`. The `dungeon` consists of `m x n` rooms laid out in a 2D grid. Our valiant knight was initially positioned in **the top-left room** and must fight his way through `dungeon` to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to `0` or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only **rightward** or **downward** in each step.

Return _the knight's minimum initial health so that he can rescue the princess_.

**Note** that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

**Example 1:**

![](https://assets.glich.co/dsa/dungeon-game/image0.jpg) 

**Input:** dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
**Output:** 7
**Explanation:** The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

**Example 2:**

**Input:** dungeon = [[0]]
**Output:** 1

**Constraints:**

* `m == dungeon.length`
* `n == dungeon[i].length`
* `1 <= m, n <= 200`
* `-1000 <= dungeon[i][j] <= 1000`

# Approaches
## Brute-Force Recursion
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.
**Time:** O(2^(m+n)) · **Space:** O(m + n)
**Pros:** Conceptually simple and a direct translation of the problem's recursive nature.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' error for all but the smallest of grids.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
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)`.

## Recursion with Memoization
This approach, also known as top-down dynamic programming, optimizes the brute-force recursion by using memoization. It stores the result for each cell `(i, j)` after computing it for the first time in a 2D array. When the function is called again for the same cell, it retrieves the result from the array instead of re-computing it, thus avoiding redundant calculations.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Efficient time complexity, solving the overlapping subproblems issue.; Maintains the recursive structure which can be intuitive.
**Cons:** Uses O(m * n) space for the memoization table.; May lead to a StackOverflowError for very large grids due to deep recursion.
### Explanation
The problem with the brute-force approach is that it solves the same subproblems repeatedly. We can fix this by storing the results. We introduce a 2D array, `memo`, of the same size as the dungeon, to cache the minimum health required for each cell `(row, col)`.

The `findMinHealth(row, col)` function is modified:
1. It first checks if `memo[row][col]` has been computed. If so, it returns the stored value.
2. If not, it proceeds with the calculation as in the brute-force method.
3. Once the result is calculated, it's stored in `memo[row][col]` for future use.

This ensures that the calculation for each cell is performed only once, dramatically improving the time complexity from exponential to polynomial.

```java
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        Integer[][] memo = new Integer[m][n];
        return findMinHealth(dungeon, 0, 0, m, n, memo);
    }

    private int findMinHealth(int[][] dungeon, int row, int col, int m, int n, Integer[][] memo) {
        if (row >= m || col >= n) {
            return Integer.MAX_VALUE;
        }

        if (memo[row][col] != null) {
            return memo[row][col];
        }

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

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

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

        return memo[row][col] = Math.max(1, neededHealth);
    }
}
```
### Algorithm
1. Create a 2D array `memo[m][n]` to store the results of subproblems, initialized with a value indicating 'not computed' (e.g., `null` or `-1`).
2. Use the same recursive function `findMinHealth(row, col)` as the brute-force approach.
3. Before any computation, check if `memo[row][col]` already contains a computed result. If yes, return it directly.
4. If the result is not in the memo table, perform the computation using the same base case and recursive step as before.
5. After computing the result, store it in `memo[row][col]` before returning it.

## 2D Dynamic Programming
This approach, also known as bottom-up dynamic programming, is an iterative alternative to memoization. It systematically fills a 2D table (`dp`) representing the minimum health required at each cell. By starting from the destination and working backward to the start, we ensure that when we calculate the value for a cell, the values for the subsequent cells (down and right) have already been computed.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Efficient O(m * n) time complexity.; Avoids recursion, thus preventing stack overflow errors and reducing overhead.; The logic is systematic and easy to follow.
**Cons:** Uses O(m * n) space, which can be substantial for large grids.
### Explanation
Instead of using recursion, we can solve the problem iteratively by building up the solution. We use a 2D array `dp` of size `m x n`, where `dp[i][j]` stores the minimum health the knight must have upon entering cell `(i, j)` to survive.

We fill this table starting from the bottom-right corner and moving towards the top-left. This order ensures that when we compute `dp[i][j]`, the values `dp[i+1][j]` (cell below) and `dp[i][j+1]` (cell to the right) are already known.

The calculation for each cell follows the same logic as the recursive approaches. The final result, the minimum initial health required at the start `(0,0)`, will be stored in `dp[0][0]` after the loops complete.

```java
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    // Princess's room
                    dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
                } else if (i == m - 1) {
                    // Last row
                    dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
                } else if (j == n - 1) {
                    // Last column
                    dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);
                } else {
                    // General case
                    int minHealthForFuture = Math.min(dp[i + 1][j], dp[i][j + 1]);
                    dp[i][j] = Math.max(1, minHealthForFuture - dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }
}
```
### Algorithm
1. Create a 2D DP table `dp[m][n]`, where `dp[i][j]` will store the minimum health needed upon entering cell `(i, j)`.
2. Iterate through the grid in reverse, from `i = m-1` down to `0` and `j = n-1` down to `0`.
3. For each cell `(i, j)`, calculate `dp[i][j]` based on the values of already computed cells `dp[i+1][j]` and `dp[i][j+1]`.
   - **Destination `(m-1, n-1)`**: `dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])`.
   - **Last Row `(i = m-1)`**: `dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])`.
   - **Last Column `(j = n-1)`**: `dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])`.
   - **General Case**: `dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])`.
4. The final answer is the value computed for the starting cell, `dp[0][0]`.

## 1D Dynamic Programming (Space Optimized)
This is the most optimized approach in terms of space. By observing the dependency in the 2D DP recurrence relation (`dp[i][j]` only depends on `dp[i+1][...]` and `dp[i][j+1]`), we can see that we only need to keep track of the previous row's DP values to compute the current row's. This allows us to reduce the space from a 2D table to a 1D array.
**Time:** O(m * n) · **Space:** O(n)
**Pros:** Optimal space complexity of O(n) (or O(min(m, n))).; Maintains the efficient O(m * n) time complexity.
**Cons:** The in-place update logic can be slightly less intuitive to grasp compared to the 2D DP approach.
### Explanation
We can optimize the space complexity of the 2D DP solution. Notice that to compute the values for row `i`, we only need the values from row `i+1`. This means we don't need to store the entire `m x n` table. A 1D array of size `n` is sufficient.

Let `dp` be a 1D array of size `n`. We iterate from the last row (`m-1`) up to the first (`0`). For each row `i`, we iterate through its columns `j` from right to left (`n-1` down to `0`).

When we compute the value for `(i, j)` and update `dp[j]`, the `dp` array cleverly holds a mix of values from row `i` and `i+1`. Specifically, `dp[j]` still holds the value from `(i+1, j)`, while `dp[j+1]` has already been updated to hold the value for `(i, j+1)`. The recurrence `min(dp[j], dp[j+1])` correctly uses the required values to compute the new `dp[j]`. This in-place update is possible because of the right-to-left column traversal.

After processing all rows, `dp[0]` will contain the final answer, `dp[0][0]`.

```java
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[] dp = new int[n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    dp[j] = Math.max(1, 1 - dungeon[i][j]);
                } else if (i == m - 1) {
                    dp[j] = Math.max(1, dp[j + 1] - dungeon[i][j]);
                } else if (j == n - 1) {
                    dp[j] = Math.max(1, dp[j] - dungeon[i][j]);
                } else {
                    int minHealthForFuture = Math.min(dp[j], dp[j + 1]);
                    dp[j] = Math.max(1, minHealthForFuture - dungeon[i][j]);
                }
            }
        }
        return dp[0];
    }
}
```
### Algorithm
1. Create a 1D array `dp` of size `n` (number of columns).
2. Iterate through the grid rows in reverse, from `i = m-1` down to `0`.
3. For each row `i`, iterate through its columns in reverse, from `j = n-1` down to `0`.
4. Update `dp[j]` using the same logic as the 2D DP, but leveraging the 1D array. When calculating the new `dp[j]` (for row `i`), the old `dp[j]` holds the value from row `i+1`, and `dp[j+1]` holds the already updated value for the current row `i`.
   - **General Case Update**: `dp[j] = max(1, min(dp[j], dp[j+1]) - dungeon[i][j])`.
   - Handle boundary cases (last row, last column) appropriately within the loops.
5. After all iterations, `dp[0]` will hold the final answer.

# Solutions
### CSharp

```csharp
public class Solution { public int CalculateMinimumHP ( int [][] dungeon ) { int m = dungeon . Length , n = dungeon [ 0 ]. Length ; int [][] dp = new int [ m + 1 ][]; for ( int i = 0 ; i < m + 1 ; ++ i ) { dp [ i ] = new int [ n + 1 ]; Array . Fill ( dp [ i ], 1 << 30 ); } 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 ) { dp [ i ][ j ] = Math . Max ( 1 , Math . Min ( dp [ i + 1 ][ j ], dp [ i ][ j + 1 ]) - dungeon [ i ][ j ]); } } return dp [ 0 ][ 0 ]; } }
```

### Java

```java
class Solution {
public
  int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    int[][] dp = new int[m + 1][n + 1];
    for (var e : dp) {
      Arrays.fill(e, 1 << 30);
    }
    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) {
        dp[i][j] =
            Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
      }
    }
    return dp[0][0];
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int: m, n = len(dungeon), len(dungeon[0]) dp = [[inf] * (n + 1) for _ in range(m + 1)] dp[m][n - 1] = dp[m - 1][n] = 1 for i in range(m - 1, - 1, - 1): for j in range(n - 1, - 1, - 1): dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]) return dp[0][0]

```