LeetCode June Challenge - Day 21

Problem: LeetCode June Challenge - Day 21

Solution:

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        if(dungeon.empty() || dungeon[0].empty()) return 0;
        int n = dungeon.size(), m = dungeon[0].size();
        int dp[n][m];

        dp[n-1][m-1] = min(0,dungeon[n-1][m-1]);
        for(int i=n-2; i>=0; --i)
            dp[i][m-1] = min(0, dungeon[i][m-1]+dp[i+1][m-1]);
        for(int j=m-2; j>=0; --j)
            dp[n-1][j] = min(0, dungeon[n-1][j]+dp[n-1][j+1]);
        for(int i=n-2; i>=0; --i)
            for(int j=m-2; j>=0; --j)
                dp[i][j]=min(0,dungeon[i][j]+max(dp[i+1][j], dp[i][j+1]));
        return -dp[0][0]+1;
    }
};