Dungeon Game

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.

题目大意：

恶魔抓走了公主(P)并把她囚禁在地牢的右下角。地牢包含M x N个房间，排列成一个二维的格子。我们英勇的骑士(K)一开始位于左上角的房间里，需要一路披荆斩棘营救公主。

骑士拥有一个正整数的初始生命值。如果在任何一点其生命值≤0，他立刻会死去。

一些房间由恶魔守卫着，因此当骑士进入这些房间时就会损失生命值（负整数）；其他房间或者是空的（数值为0），或者包含一些魔力宝珠（magic orbs）可以增加骑士的生命值（正整数）。

为了尽可能快的解救公主，骑士决定每一步只向右或者向下移动。

编写一个函数决定骑士的最小初始生命值，确保他可以成功营救公主。

例如，给定下面的地牢，骑士的初始生命值至少应当为7，如果他按照下面的最优路线行进：右 -> 右 -> 下 -> 下.

备注：

骑士的生命值没有上界

任何房间都可能包含威胁或者补给，即使骑士进入的第一个房间或者囚禁公主的最后一个房间也一样。

题目思路：

乍一看，这个问题和"Maximum/Minimum Path Sum"问题很相似。然而，具有全局最大HP（生命值）收益的路径并不一定可以保证最小的初始HP，因为题目中具有限制条件：HP不能≤0。例如，考虑下面的两条路径：0 -> -300 -> 310 -> 0 和 0 -> -1 -> 2 -> 0。这两条路径的净HP收益分别是-300 + 310 = 10 与 -1 + 2 = 1。第一条路径的净收益更高，但是它所需的初始HP至少是301，才能抵消第二个房间的-300HP损失，而第二条路径只需要初始HP为2就可以了。

幸运的是，这个问题可以通过“table-filling”（表格填充）动态规划算法解决，与其他"grid walking"（格子行走）问题类似：

首先，我们应该维护一个2维数组D，与地牢数组的大小相同，其中D[i][j]代表可以保证骑士在进入房间(i,j)之前，探索其余地牢时能够存活下来的最小HP。显然D[0][0]就是我们随后需要的最终答案。因此，对于这个问题，我们需要从右下角到左上角填充表格。

然后，我们来计算离开房间(i,j)时的最小HP。从这一点出发只有两条路径可选：(i + 1, j)和(i, j + 1)。当然我们会选择拥有更小D值的那个房间，换言之，骑士完成剩下的旅途所需的较小HP。因此我们有：

  min_HP_on_exit = min(D[i+1][j], D[i][j+1])
  
现在D[i][j]可以通过dungeon[i][j]和min_HP_on_exit，根据下面的情景得出：

如果dungeon[i][j] == 0，那么在这个房间里很安全。 骑士离开这个房间时的HP和他进入房间时的HP保持一致， 也就是说 D[i][j] = min_HP_on_exit.

如果dungeon[i][j] < 0，那么骑士在进入该房间之前的HP > 离开房间时的HP，min_HP_on_exit才能抵消他在该房间中的HP损失。 最小HP花费就是 "-dungeon[i][j]"， 因此我们有公式 D[i][j] = min_HP_on_exit - dungeon[i][j].

如果dungeon[i][j] > 0, 那么骑士在进入房间(i, j) 时的HP只需为min_HP_on_exit - dungeon[i][j]，因为他可以在该房间内获得数值为"dungeon[i][j]"的HP收益。 不过，这种情况下min_HP_on_exit - dungeon[i][j]的数值可能≤0。 此时，我们需要把值置为1以确保D[i][j]为正整数: D[i][j] = max(min_HP_on_exit - dungeon[i][j], 1)。

注意 dungeon[i][j] > 0 条件下的等式实际上可以覆盖其他两种情况。 因此我们可以把三种情况归纳为同一个等式： 亦即:

D[i][j] = max(min_HP_on_exit - dungeon[i][j], 1)
dungeon[i][j]可以为任意值。

D[0][0]就是最终答案。 此外，像许多其他"table-filling"问题一样，二维数组D可以用一维滚动数组替代。

C++实现代码：

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        if(dungeon.empty()||dungeon[0].empty())
            return 1;
        int m=dungeon.size();
        int n=dungeon[0].size();
        int i,j;
        int dp[m][n];
        dp[m-1][n-1]=max(1-dungeon[m-1][n-1],1);
        for(i=m-2;i>=0;i--)
            dp[i][n-1]=max(dp[i+1][n-1]-dungeon[i][n-1],1);
        for(j=n-2;j>=0;j--)
            dp[m-1][j]=max(dp[m-1][j+1]-dungeon[m-1][j],1);
        for(i=m-2;i>=0;i--)
        {
            for(j=n-2;j>=0;j--)
            {
                //可以从上下两个方向到达
                dp[i][j]=min(max(dp[i][j+1]-dungeon[i][j],1),max(dp[i+1][j]-dungeon[i][j],1));
            }
        }
        return dp[0][0];
    }
};

int main()
{
    Solution s;
    vector<vector<int> > vec={{-2,-3,3},{-5,-10,1},{10,30,-5}};
    cout<<s.calculateMinimumHP(vec)<<endl;
}