Dungeon Game: Minimum Health to Survive

Imagine a brave knight entering a dangerous dungeon. The dungeon is represented as a 2D grid, where each cell contains either a positive integer (health potion) or a negative integer (a monster's attack). The knight starts at the top-left corner and must reach the princess in the bottom-right corner. To survive, the knight's health must never drop to 0 or below at any point during their journey.

This problem challenges you to find the minimum initial health the knight needs to have to guarantee survival. This is a classic dynamic programming problem with a twist: you need to work backward from the destination to find the optimal path.

Problem Description

You are given a 2D grid dungeon representing the dungeon.

• dungeon[i][j] is an integer representing the change in health upon entering cell (i, j).
• Positive values are health potions.
• Negative values represent monster attacks.
• The knight starts at dungeon[0][0] and wants to reach dungeon[rows-1][cols-1].
• The knight can only move right or down at each step.
• The knight's health must always be greater than 0. If it drops to 0 or less at any point, the knight dies.

You need to determine the minimum initial health the knight must have at the start (dungeon[0][0]) to reach the princess at dungeon[rows-1][cols-1] alive.

Key Requirements:

• Calculate the minimum starting health.
• The knight's health must remain strictly positive (> 0) at all times.

Expected Behavior:

The function should return a single integer representing the minimum initial health.

Edge Cases:

• A dungeon with only one cell.
• Dungeons where all cells have positive health gains.
• Dungeons where all cells have negative health losses.

Examples

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation:
The knight needs a minimum initial health of 7. One possible path is:
(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
Health progression:
Start with 7.
Cell (0,0): 7 + (-2) = 5
Cell (0,1): 5 + (-3) = 2
Cell (0,2): 2 + 3 = 5
Cell (1,2): 5 + 1 = 6
Cell (2,2): 6 + (-5) = 1. Reaches princess with 1 health.

If the knight starts with 6 health:
Cell (0,0): 6 + (-2) = 4
Cell (0,1): 4 + (-3) = 1
Cell (0,2): 1 + 3 = 4
Cell (1,2): 4 + 1 = 5
Cell (2,2): 5 + (-5) = 0. Knight dies.

Example 2:

Input: dungeon = [[0]]
Output: 1
Explanation:
The knight starts and ends in the same cell. Even though the health change is 0, the knight's health must always be greater than 0. Therefore, the minimum initial health is 1.

Example 3:

Input: dungeon = [[100]]
Output: 1
Explanation:
The knight starts and ends in the same cell. The health gain is 100, but the knight still needs at least 1 health to begin.

Constraints

• 1 <= rows, cols <= 200 (where rows is the number of rows and cols is the number of columns in the dungeon).
• -1000 <= dungeon[i][j] <= 1000
• The knight can only move right or down.

Notes

• This problem is best approached using dynamic programming. Consider working backward from the princess's location to the knight's starting position.
• For each cell, you need to determine the minimum health required to enter that cell such that you can still reach the princess.
• Remember that the health must always be strictly greater than 0.