Leetcode 174. 地下城游戏

动态规划问题
到此方块前的最小值=max(下方块前的最小值，右方块前的最小值)-此方块的值），若果这个最小值小于1，则置为1【为了存活】

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int L = dungeon[0].size(), row = dungeon.size();
        vector<int> dp(L, 0);
        dp[L - 1] = max(1 - dungeon.back()[L - 1], 1);
        for (int i = L - 2; i >= 0; --i)
            dp[i] = max(dp[i + 1] - dungeon.back()[i], 1);
        for (int k = row - 2; k >= 0; --k) {
            dp[L - 1] = max(dp[L - 1] - dungeon[k][L - 1], 1);
            for (int i = L - 2; i >= 0; --i)
                dp[i] = max(min(dp[i + 1], dp[i]) - dungeon[k][i], 1);
        }
        return dp[0];
    }
};