> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Dungeon Game Python Solution with Tests

> Tested Python solution for LeetCode 174 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 174, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Dynamic Programming](/catalog/topics/dynamic-programming), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/dungeon-game/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 174   # by problem number
lcpy gen -s dungeon_game   # by problem name
```

## Problem

\<p>The demons had captured the princess and imprisoned her in \<strong>the bottom-right corner\</strong> of a \<code>dungeon\</code>. The \<code>dungeon\</code> consists of \<code>m x n\</code> rooms laid out in a 2D grid. Our valiant knight was initially positioned in \<strong>the top-left room\</strong> and must fight his way through \<code>dungeon\</code> to rescue the princess.\</p>

\<p>The knight has an initial health point represented by a positive integer. If at any point his health point drops to \<code>0\</code> or below, he dies immediately.\</p>

\<p>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).\</p>

\<p>To reach the princess as quickly as possible, the knight decides to move only \<strong>rightward\</strong> or \<strong>downward\</strong> in each step.\</p>

\<p>Return \<em>the knight's minimum initial health so that he can rescue the princess\</em>.\</p>

\<p>\<strong>Note\</strong> 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.\</p>

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.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.
```

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

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/dungeon_game/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/dungeon_game/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m * n)
    # Space: O(n)
    def calculate_minimum_hp(self, dungeon: list[list[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        # need[j]: minimum health required upon entering cell (i, j); right
        # sentinel need[n] = INF means "no cell to the right" outside the grid.
        need = [10**9] * (n + 1)
        need[n - 1] = 1
        for i in range(m - 1, -1, -1):
            need[n] = 10**9
            for j in range(n - 1, -1, -1):
                need[j] = max(1, min(need[j], need[j + 1]) - dungeon[i][j])
        return need[0]
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n) | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.