Straightforward DP solution


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

  • 0
    Z
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.