Leetcode-174-Dungeon Game

题意简单说来就是给定的方格，每个格子里的数字代表HP值增减的数量，从左上角格子出发，每一步向右或向下走，走到右下角格子，要求路程中HP不低于1（否则死亡），问出发时HP值最小是多少。

这是典型的DP问题。但需要注意DP的方向应该是从右下角向左上角，而不是相反。这道题我们需要考虑的过程是这样的，要求出发时最小的HP值，我们只需要到达右下角的HP值为1即可（当然也可以大于1，如果格子中是正数），接下来我们从右下到左上做DP，每一步记录到当前格子所需最小的HP值，记为若出现的情形（即所需最小HP为负），只需要更新其值为1即可（这是题目的要求）。

代码如下：

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