leetcode174. 地下城游戏

分析

由于从骑士开始走的话需要提前知道路径和起始健康点数，所以可以从公主去找骑士，只需要朝两个方向中所需的最小健康点方向即可。

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