Dungeon Game Minimum Health

Find the minimum initial health required to rescue the princess from a dungeon with health-draining rooms.

dynamic-programming matrix grid optimization minimum-path

The king has trapped you in a dungeon! The dungeon is a 2D grid of size `rows x cols`. You start at the top-left cell `(0, 0)` and must reach the bottom-right cell `(rows-1, cols-1)`. You can only move right or down.

Each cell contains an integer `dungeon[i][j]`. If positive, it increases your health; if negative, it decreases your health. You start with an unknown initial health `H`. Your health must stay strictly greater than 0 at all times, including after entering the start cell and after entering the destination cell. The health effect of the start cell applies immediately when you begin, so you need enough health to survive that cell as well.

Write a function `min_initial_health(dungeon)` that returns the **minimum initial health** `H` (a positive integer) that guarantees you can reach the destination with health always ≥ 1.

For example, if `dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]`, the minimum initial health is 7.

Note: The solution must use dynamic programming. The time complexity should be O(rows × cols) and space O(rows × cols) or O(cols).

Constraints

- 1 ≤ rows, cols ≤ 200
- -10^5 ≤ dungeon[i][j] ≤ 10^5
- The answer fits in a 32-bit signed integer.

Example

>>> min_initial_health([[-2, -3, 3], [-5, -10, 1], [10, 30, -5]])
7
>>> min_initial_health([[0, 0], [0, 0]])
1
>>> min_initial_health([[-5, -10, -15]])
31
>>> min_initial_health([[5, 10, 15]])
1

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think backwards from the destination to the start: define dp[i][j] as the minimum health required before entering cell (i,j) to reach the end.

For the destination, you need max(1, 1 - dungeon[-1][-1]) health before entering it.

For each cell, the required health before entering is max(1, min(required after moving right, required after moving down) - dungeon[i][j]).

Use a 1D array for the DP to save memory, filling from bottom-right to top-left.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.