C++ DP bottom up (easy to understand) & recursion + memoization


  • 0
    H

    Bottom Up:

    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            int m = dungeon.size();
            if(m == 0) return 0;
            int n = dungeon[0].size();
            if(n == 0) return 0;
            vector<vector<int>> dp(m, vector<int>(n));
            if(dungeon[m-1][n-1] <= 0){//find the minimum health needed when knight comes here
                dp[m-1][n-1] = -dungeon[m-1][n-1] + 1;
            } else {//I need at least 1 HP when knight come here as the health never drops
                dp[m-1][n-1] = 1;//1 and not 0 because the problem says knight dies if health <= 0
            }
            for(int i = m-1; i >= 0; i--){
                for(int j = n-1; j >= 0; j--){
                    if(i == m-1 && j == n-1) continue;
                    int minNeedInEitherDir = INT_MAX;//find minimum HP needed if knight goes down or right
                    if(i != m-1){
                        minNeedInEitherDir = min(minNeedInEitherDir, dp[i+1][j]);
                    }
                    if(j != n-1){
                        minNeedInEitherDir = min(minNeedInEitherDir, dp[i][j+1]);
                    }
                    if(dungeon[i][j] >= minNeedInEitherDir){//if the dungeon cell's orb can give me the health needed 
                        dp[i][j] = 1;           //to endure the rest of the path, I need only 1 HP when I come here
                    } else { //if this dungeon cell has a demon or doesn't have enough HP, calculate the min needed 
                            // to reach from here to the princess sagfely.
                        dp[i][j] = minNeedInEitherDir - dungeon[i][j];
                    }
                }
            }
            return dp[0][0];
        }
    };
    

    Recursion + Memoization:

    class Solution {
    public:
        int solve(vector<vector<int>>& dungeon, int x, int y, int m, int n, vector<vector<int>>& dp){
            if(dp[x][y] != -1) return dp[x][y];
            int leftMinNeeded = INT_MAX;
            if(x+1 <= m){
                leftMinNeeded = solve(dungeon, x+1, y, m, n, dp);
            }
            int rightMinNeeded = INT_MAX;
            if(y+1 <= n){
                rightMinNeeded = solve(dungeon, x, y+1, m, n, dp);
            }
            int dirMinNeeded = min(leftMinNeeded, rightMinNeeded);
            if(dungeon[x][y] >= dirMinNeeded){
                dp[x][y] = 1;
            } else {
                dp[x][y] = dirMinNeeded - dungeon[x][y];
            }
            return dp[x][y];
        }
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            int m = dungeon.size();
            if(m == 0) return 0;
            int n = dungeon[0].size();
            if(n == 0) return 0;
            vector<vector<int>> dp(m, vector<int>(n, -1));
            if(dungeon[m-1][n-1] <= 0){
                dp[m-1][n-1] = -dungeon[m-1][n-1] + 1;
            } else {
                dp[m-1][n-1] = 1;
            }
            int minNeeded = solve(dungeon, 0, 0, m-1, n-1, dp);
            return minNeeded;
        }
    };
    

Log in to reply
 

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