174. Dungeon Game

https://leetcode.com/problems/dungeon-game/description/

给定二维矩阵，起点为左上角，每步可往下和右走，根据格子的值会相应扣血或回血，问活着(hp>=1)从左上角走到右下角hp初始值至少是多少。action为从上或左选个格子跳转过来，要求到达终点时hp也至少为1，限制来自于终点而不是起点，所以从终点开始写状态转移直到起点。dp[i][j]表示从(i, j)出发时保证活着到"终点"的最小hp。扣血相当于要更多的初始hp，回血需要少的hp，因此dp[i,j] = min(dp[i+1,j], dp[i, j -1]) 减去dungeon[i,j]。又因为题目要求到达每个格子hp至少为1，dp[i][j] = max(1, 上一个状态- dungeon(i, j))。

思路参考了花花的。

/*
 * @lc app=leetcode id=174 lang=cpp
 *
 * [174] Dungeon Game
 */
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        const int M = dungeon.size(), N = M == 0 ? 0 : dungeon[0].size();
        vector<vector<int>> dp(M + 1, vector<int>(N + 1, INT_MAX));
        dp[M][N - 1] = dp[M - 1][N] = 1;
        for (int i = M - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        
        return dp[0][0];
    }
};