Minimize Initial Health along a Right-Down Dungeon Path
Company: Intuit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
A traveler starts in the top-left room of a rectangular dungeon and must reach the bottom-right room, moving only right or down. Entering a room adds its signed value to the traveler's health. Health must remain strictly positive after every room, including the first and last. Return the smallest positive integer starting health that permits a successful path.
```cpp
int calculateMinimumHP(vector<vector<int>>& dungeon);
```
### Examples
```text
Input: dungeon = [[-3,5],[-2,-4]]
Output: 4
```
Right then down changes health 4→1→6→2.
```text
Input: dungeon = [[5]]
Output: 1
```
### Constraints
- Both dimensions are between 1 and 200.
- Each room value is between -1000 and 1000.
- The start and destination may themselves contain damage or healing.
Overview: Find minimum strictly positive starting health by propagating dungeon survival requirements backward.