The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path `RIGHT-> RIGHT -> DOWN -> DOWN`.

Notes:

• The knight’s health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

1. 由于是逆推，所以方向是只能向左和向上，而且每步要减去该格的value，如起始状态就是 1 – (-5) = 6，意思就是到达最后一格前至少要有6的血量。
2. 当减去该格value小于1的时候说明即使只有最少的1点血都可以在该格存活，直接把该格DP值设为1即可。

Solution:

``````
class Solution {
public:
int DP[1000];
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if(dungeon.size() == 0) return 1;
if(dungeon[0].size() == 0) return 1;
int n = dungeon.size();
int m = dungeon[0].size();

DP[m - 1] = 1;
for(int i = n - 1; i >= 0; --i)
{
for(int j = m - 1; j >= 0; --j)
{
if(j != m - 1)
{
if(i == n - 1) DP[j] = DP[j + 1];
else DP[j] = min(DP[j + 1], DP[j]);
}
DP[j] -= dungeon[i][j];
if(DP[j] <= 0) DP[j] = 1;
}
}
return DP[0];
}
};
``````