# Best solution I have found with explanations

• 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];
}``````

• Very concise and understandable code.

There is no need to build an extra auxiliary minInitHealth matrix. Just use dungeon to save the DP result from bottom right to top left

``````int calculateMinimumHP(vector<vector<int> > &dungeon) {

if(dungeon.size()==0) return 0;

int row=dungeon.size();
int col=dungeon[0].size();

for(int i=row-1; i>=0; i--) {

for(int j=col-1; j>=0; j--) {

if(i==row-1 && j==col-1) dungeon[i][j]=max(1, 1-dungeon[i][j]);
else if(i==row-1) dungeon[i][j]=max(1, dungeon[i][j+1]-dungeon[i][j]);
else if(j==col-1) dungeon[i][j]=max(1, dungeon[i+1][j]-dungeon[i][j]);
else dungeon[i][j]=max(1, min(dungeon[i+1][j], dungeon[i][j+1])-dungeon[i][j]);
}
}

return dungeon[0][0];
}
``````

Thanks

• best solution and explanation.

• very terse and clear solution.

• initialHealth[i][j] = initialHealth[i][j] - dungeon[i-1][j]
the first "initialHealth[i][j]" should be "initialHealth[i - 1][j]"

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.