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.

这题目看着挺花哨的，其实和64. Minimum Path Sum是一样的。我们仍然开一个DP[j]数组（为什么只开一维数组的解释在64题题解里），不同的是虽然knight的顺序是从左上到右下，但求的却是起始最小血量，所以我们需要反过来逆推出这个血量，也就是说我们要从右下出发回到左上，求出这个过程中到达左上角时候的最小值。这个过程需要注意两点：

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

其它的部分和64题几乎一样，最后返回DP[j – 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];
}
};
```