DFS with memoization


  • 0
    S
    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            if (!dungeon.size()) return 0;
            vector<vector<int>> mp(dungeon.size(), 
                                   vector<int> (dungeon[0].size(), -1));
            int res = dfs(0,0,dungeon, mp);
            
            if (res <= 0) {
                return -res+1;
            } else {
                return 1;
            }
        }
        
        int dfs(int i, int j, vector<vector<int>>& d, vector<vector<int>>& mp) {
            int p1 = INT_MIN;
            int p2 = INT_MIN;
            
            if (mp[i][j] != -1) {
                return mp[i][j];
            }
            
            if (i == d.size()-1 && j == d[0].size()-1) {
                return d[i][j];
            }
    
            if (i+1 < d.size()) p1 = dfs(i+1, j, d, mp);
            if (j+1 < d[0].size()) p2 = dfs(i, j+1, d, mp);
            
            int p = min(d[i][j], d[i][j] + max(p1, p2));
            mp[i][j] = p;    
            return p;
        }
    };
    
    

Log in to reply
 

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