# LeetCode 174: Dungeon Game

## Problem Restatement

We are given a 2D grid:

```python
dungeon
```

A knight starts at the top-left cell:

```python
(0, 0)
```

and wants to rescue the princess at the bottom-right cell.

The knight may move only:

| Direction | Allowed |
|---|---|
| Right | Yes |
| Down | Yes |
| Left | No |
| Up | No |

Each cell changes the knight’s health:

| Cell value | Effect |
|---|---|
| Negative | Lose health |
| Positive | Gain health |
| Zero | No change |

The knight dies immediately if health becomes:

```python
<= 0
```

We must return the minimum initial health required so the knight can reach the princess alive.

LeetCode guarantees the grid dimensions are at most `200 x 200`. ([leetcode.com](https://leetcode.com/problems/dungeon-game/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | 2D integer matrix `dungeon` |
| Output | Minimum initial health |
| Start | Top-left cell |
| Destination | Bottom-right cell |
| Allowed moves | Right or down |
| Survival rule | Health must always stay at least `1` |

Example function shape:

```python
def calculateMinimumHP(dungeon: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

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

The optimal path is:

```text
RIGHT -> RIGHT -> DOWN -> DOWN
```

Health changes:

| Cell | Health change |
|---|---:|
| `-2` | lose 2 |
| `-3` | lose 3 |
| `3` | gain 3 |
| `1` | gain 1 |
| `-5` | lose 5 |

The minimum starting health that keeps health positive throughout is:

```python
7
```

Example 2:

```python
dungeon = [[0]]
```

No damage occurs.

The knight still needs at least:

```python
1
```

health to survive.

Return:

```python
1
```

## First Thought: Forward Dynamic Programming

One possible idea is:

```text
dp[i][j] = best health when reaching cell (i, j)
```

But this does not work well.

The problem is that maximizing current health does not guarantee future survival.

Example:

```text
large positive now
huge negative later
```

A locally good path may still fail later.

We need to think backward.

## Key Insight

Instead of asking:

```text
How much health do we have here?
```

ask:

```text
How much health must we have before entering this cell?
```

This reverse perspective makes the transitions clean.

Define:

```python
dp[i][j]
```

as the minimum health needed before entering cell `(i, j)` so the knight can still reach the princess alive.

The knight may move:

```text
right
down
```

So from `(i, j)` we need enough health to survive whichever next cell requires less health.

Suppose the next required health is:

```python
need
```

If the current cell gives:

```python
dungeon[i][j]
```

then before entering this cell we need:

```python
need - dungeon[i][j]
```

But health must never fall below `1`.

So:

```python
dp[i][j] = max(1, need - dungeon[i][j])
```

## Reverse Dynamic Programming Transition

For a normal cell:

```python
need = min(dp[i + 1][j], dp[i][j + 1])
```

because we choose the better next direction.

Then:

```python
dp[i][j] = max(1, need - dungeon[i][j])
```

## Base Case

At the princess cell:

```python
(m - 1, n - 1)
```

Suppose the cell value is:

```python
x
```

After entering the cell, health must remain at least `1`.

So before entering, we need:

```python
max(1, 1 - x)
```

Examples:

| Cell value | Required health before entering |
|---|---:|
| `-5` | `6` |
| `0` | `1` |
| `10` | `1` |

## Algorithm

Let:

```python
m = number of rows
n = number of columns
```

Create:

```python
dp[m][n]
```

where:

```python
dp[i][j]
```

stores the minimum health required before entering `(i, j)`.

Fill the table backward:

1. Initialize the princess cell.
2. Fill the last row.
3. Fill the last column.
4. Fill the remaining cells from bottom-right to top-left.

Return:

```python
dp[0][0]
```

## Walkthrough

Use:

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

Start from bottom-right:

```python
dp[2][2] = max(1, 1 - (-5))
          = 6
```

Last row:

```python
dp[2][1] = max(1, 6 - 30)
          = 1
```

```python
dp[2][0] = max(1, 1 - 10)
          = 1
```

Last column:

```python
dp[1][2] = max(1, 6 - 1)
          = 5
```

```python
dp[0][2] = max(1, 5 - 3)
          = 2
```

Now inner cells.

Cell `(1,1)`:

```python
need = min(1, 5) = 1

dp[1][1] = max(1, 1 - (-10))
          = 11
```

Cell `(1,0)`:

```python
need = min(1, 11) = 1

dp[1][0] = max(1, 1 - (-5))
          = 6
```

Cell `(0,1)`:

```python
need = min(11, 2) = 2

dp[0][1] = max(1, 2 - (-3))
          = 5
```

Cell `(0,0)`:

```python
need = min(6, 5) = 5

dp[0][0] = max(1, 5 - (-2))
          = 7
```

Return:

```python
7
```

## Correctness

The dynamic programming state:

```python
dp[i][j]
```

represents the minimum health needed before entering cell `(i, j)` so the knight can still reach the princess alive.

At the princess cell, the knight must leave the cell with health at least `1`. Therefore:

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

For any other cell, the knight may move right or down. The next step should minimize the required health, so the algorithm chooses:

```python
min(dp[i + 1][j], dp[i][j + 1])
```

Suppose this value is `need`.

After applying the current cell’s effect:

```python
dungeon[i][j]
```

the knight must still have at least `need` health. Therefore, before entering the current cell, the knight needs:

```python
need - dungeon[i][j]
```

health.

Because health must always stay positive, the minimum valid health is at least `1`. Thus:

```python
dp[i][j] = max(1, need - dungeon[i][j])
```

The table is filled backward, so every required future state is already known when computing the current state.

Therefore, `dp[0][0]` equals the minimum initial health required to rescue the princess.

## Complexity

Let:

```python
m = number of rows
n = number of columns
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | Every cell is processed once |
| Space | `O(m * n)` | The DP table stores one value per cell |

## Implementation

```python
class Solution:
    def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
        m = len(dungeon)
        n = len(dungeon[0])

        dp = [[0] * n for _ in range(m)]

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

        for j in range(n - 2, -1, -1):
            dp[m - 1][j] = max(
                1,
                dp[m - 1][j + 1] - dungeon[m - 1][j],
            )

        for i in range(m - 2, -1, -1):
            dp[i][n - 1] = max(
                1,
                dp[i + 1][n - 1] - dungeon[i][n - 1],
            )

        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                need = min(
                    dp[i + 1][j],
                    dp[i][j + 1],
                )

                dp[i][j] = max(
                    1,
                    need - dungeon[i][j],
                )

        return dp[0][0]
```

## Code Explanation

The DP table stores minimum required health before entering each cell:

```python
dp = [[0] * n for _ in range(m)]
```

Initialize the princess cell:

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

The last row may move only right:

```python
dp[m - 1][j]
```

depends on:

```python
dp[m - 1][j + 1]
```

The last column may move only down:

```python
dp[i][n - 1]
```

depends on:

```python
dp[i + 1][n - 1]
```

Inner cells choose the cheaper future path:

```python
need = min(
    dp[i + 1][j],
    dp[i][j + 1],
)
```

Then compute the health needed before entering the current cell:

```python
dp[i][j] = max(
    1,
    need - dungeon[i][j],
)
```

Finally:

```python
return dp[0][0]
```

returns the minimum initial health.

## Space Optimization

We only need the current row and the next row.

So space can be reduced to:

```python
O(n)
```

using a 1D DP array.

## Testing

```python
def run_tests():
    sol = Solution()

    assert sol.calculateMinimumHP([
        [-2, -3, 3],
        [-5, -10, 1],
        [10, 30, -5],
    ]) == 7

    assert sol.calculateMinimumHP([[0]]) == 1

    assert sol.calculateMinimumHP([[100]]) == 1

    assert sol.calculateMinimumHP([[-5]]) == 6

    assert sol.calculateMinimumHP([
        [1, -3, 3],
        [0, -2, 0],
        [-3, -3, -3],
    ]) == 3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Mixed gains and losses |
| `[[0]]` | Neutral single cell |
| `[[100]]` | Large positive cell |
| `[[-5]]` | Single damaging cell |
| Mixed grid | Multiple possible paths |