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

• 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;
}
};
``````

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