http://leetcodesolution.blogspot.com/2015/01/leetcode-dungeon-game.html

seems pretty simple... and easy to understand explanations...

It is easy to know that at grid P, since " at any point his health point drops to 0 or below, he dies immediately", the remaining health value should be at least 1, that is, initialHealth + dungeon >= 1, we have initialHealth = max(1, 1 - dungeon[i][j]). (Notice, at any grid, the initial health should be at least 1 (for example, test case [1,0,0] require initial health 1 even though it has positive remaining health at grid[0][1] and grid[0][2])

Similarly, to satisfy the initial health of dungeon[i][j], the initial health of dungeon[i-1][j] (or dungeon[i][j-1]) should be at least initialHealth[i-1][j] + dungeon[i-1][j] = initialHealth[i][j], that is, initialHealth[i][j] = initialHealth[i][j] - dungeon[i-1][j].

In addition, if grid[i][j] can go both grid[i+1][j] and grid[i][j+1] to P, we should choose a path with less initial health between grid[i+1][j] and grid[i][j+1] since it require less initial health of grid[i][j].

We can simply code the solution by having the dynamic programming equations.

```
int calculateMinimumHP(vector &dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
vector minInitHealth(m, vector<int>(n,0));
for(int i=m-1; i>=0; i--)
{
for (int j=n-1; j>=0; j--)
{
if (i == m-1 && j == n-1)
{
minInitHealth[i][j] = max(1, 1 - dungeon[i][j]);
}
else if (i == m-1)
{
minInitHealth[i][j] = max(1, minInitHealth[i][j+1] - dungeon[i][j]);
}
else if (j == n-1)
{
minInitHealth[i][j] = max(1, minInitHealth[i+1][j] - dungeon[i][j]);
}
else
{
minInitHealth[i][j] = max(1, min(minInitHealth[i+1][j],minInitHealth[i][j+1]) - dungeon[i][j]);
}
}
}
return minInitHealth[0][0];
}
```