A simplified C++ solution, 9 lines, O(mn) in time and O(n) in space


  • 0
    R

    dp[i][j] = { min health to rescue princess, when knignt enters dungeon[i][j]}

    dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);

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

Log in to reply
 

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