https://leetcode.com/problems/dungeon-game/
喜欢做这种有情节的题目。
6.4就要做indeed笔试，现在心情比较激动。
最近玩的Dragon Hills已经过到了level70。

1.右下到左上，常规解法

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int> > dp(m, vector<int>(n, 1));
        //init
        dp[m-1][n-1] = dungeon[m-1][n-1] >= 0 ? 1 : - dungeon[m-1][n-1] + 1;
        for(int i = n-2; i >= 0; i--) 
            dp[m-1][i] = dungeon[m-1][i] >= dp[m-1][i+1] ? 1 : dp[m-1][i+1] - dungeon[m-1][i];
        for(int i = m-2; i >= 0; i--)
            dp[i][n-1] = dungeon[i][n-1] >= dp[i+1][n-1] ? 1 : dp[i+1][n-1] - dungeon[i][n-1];
        //dp
        for(int i = m-2; i >= 0; i--) {
            for(int j = n-2; j >= 0; j--) {
                int d = min(dp[i][j+1],dp[i+1][j]);
                if(dungeon[i][j] >= d)
                    dp[i][j] = 1;
                else
                    dp[i][j] = d - dungeon[i][j];
            }
        }
        return dp[0][0];
    } 
};    

2.压缩了一行空间

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<int> dp(n, 1);
        //init
        dp[n-1] = dungeon[m-1][n-1] >= 0 ? 1 : - dungeon[m-1][n-1] + 1;
        for(int i = n-2; i >= 0; i--) 
            dp[i] = dungeon[m-1][i] >= dp[i+1] ? 1 : dp[i+1] - dungeon[m-1][i];
        //dp
        for(int i = m-2; i >= 0; i--) {
            dp[n-1] = dungeon[i][n-1] >= dp[n-1] ? 1 : dp[n-1] - dungeon[i][n-1];
            for(int j = n-2; j >= 0; j--) {
                int d = min(dp[j+1],dp[j]);
                if(dungeon[i][j] >= d)
                    dp[j] = 1;
                else
                    dp[j] = d - dungeon[i][j];
            }
        }
        return dp[0];
    } 
};

3.标签里给的Binary Search
看到Dicuss里的一个Binary Search解答，觉得不是很可靠而且时间复杂度好高。
https://leetcode.com/discuss/25671/a-simple-c-solution-using-binary-search