算法: Dungeon Game

Dungeon Game
计算出二维数组从0.0 点到 m.n 点的最小代价.. 并且每经过一个格子所剩余的代价必须是> 0 的

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        const vector<vector<int>>& d = dungeon;
        const int m = d.size();
        const int n = d[0].size();
        vector<vector<int>> hp(m+1, vector<int>(n+1, INT_MAX));
        
        hp[m][n-1] = hp[m-1][n] = 1;
        for (int y=m-1;y>=0;y--){
            for (int x=n-1;x>=0;x--){
                hp[y][x] = max(1, min(hp[y][x+1], hp[y+1][x]) - d[y][x]);
            }
        }
        return hp[0][0];
    }
};