LeetCode 174. 地下城游戏（DP）

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 
右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)	-3	  3
-5	   -10	  1
10	    30	 -5 (P)

说明:
骑士的健康点数没有上限。

任何房间都可能对骑士的健康点数造成威胁，
也可能增加骑士的健康点数，
包括骑士进入的左上角房间以及公主被监禁的右下角房间。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& grid) {
    	int m = grid.size(), n = grid[0].size(), i, j, minlife;
    	vector<vector<int>> dp(m+1,vector<int>(n+1, INT_MAX));
    	dp[m][n-1] = dp[m-1][n] = 1;//处理边界更方便
    	for(i = m-1; i >= 0; --i)
    	{
    		for(j = n-1; j >= 0; --j)
    		{
    			minlife = min(dp[i+1][j], dp[i][j+1]);
    			//使用较小的
    			dp[i][j] = max(minlife-grid[i][j], 1);
    			//在 i,j,处你的生命值至少需要为1
    		}
    	}
    	return dp[0][0];
    }
};