C++ dp solution


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

Log in to reply
 

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