题解
看到裸的二维数组心情激动，下意识认为应该是个非常水的DP。写着写着发现不对，状态表示有些复杂，于是点开Tags瞄了一眼，原来还要用到二分思想，于是就明白怎么回事了。
首先确定答案的上下界：如果地图上面全是正数，显然初始只要1个生命值就能走完全程；最差情况下全图都是负数，但我们没必要DP找出最节省的负数路径，其实把所有负数加起来就可以作为生命值的上界，反正也就大一点点常数。
有了上下界之后开始二分，这时就需要一个判定答案是否有效的函数。我们用DP思想来实现这个判定，每个格子的状态可以由其上方和左方的格子转移过来，前提是转移过来的那个格子必须合法，也就是其上的剩余生命值大于零，并且转移之后我们要更新当前格子的剩余生命值。最后，我们检查终点的剩余生命值是否大于零，就可以看出这个答案是否有效。
Update: 其实这题不用二分，纯DP也是可以做的。只是状态表示略微复杂，而且没有二分的思路简洁漂亮。
代码
static const int MAX = 2000;
int dp[MAX][MAX];
const int INF = 0x3f3f3f3f;
class Solution {
public:
bool checkLegal( int hp, vector<vector<int> > &dungeon ) {
int n = dungeon.size();
int m = dungeon[0].size();
dp[0][0] = dungeon[0][0] + hp;
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < m; j++ ) {
if ( i || j ) dp[i][j] = -INF;
if ( j && dp[i][j - 1] > 0 ) dp[i][j] = max(dp[i][j], dp[i][j - 1] + dungeon[i][j]);
if ( i && dp[i - 1][j] > 0 ) dp[i][j] = max(dp[i][j], dp[i - 1][j] + dungeon[i][j]);
}
return dp[n - 1][m - 1] > 0;
}
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int low = 1, high = 2;
int n = dungeon.size();
int m = dungeon[0].size();
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < m; j++ ) if ( dungeon[i][j] < 0 )
high -= dungeon[i][j];
int res = -1;
while ( low < high ) {
int mid = ( low + high ) >> 1;
if ( checkLegal(mid, dungeon) ) {
res = mid;
high = mid;
} else {
low = mid + 1;
}
}
return res;
}
};