Dungeon Game | Dynamic programming | Leetcode #174
This video explains a very important programming interview problem which is the dungeon game from leetcode #174.In this game, we are given a matrix of size N * M. Princess is present in the last cell (N, M) and the knight who will save her will start at (0,0).Each cell of the matrix is room of dungeon.Each of the room can be occupied by a demon or a magic orb.Knight looses an equal amount of health to fight demon and gains equal amount of health from a magical orb.As soon as the health of the knight reaches 0, he dies.We need to find the minimum health with which the knight should start such that there is atleast one possible path from the cell (0,0) to cell (N, N), so that the knight saves the princess.This is a variant of Minimum cost path problem.This can be solved using binary search and also using recursion.The best method to solve this is by using dynamic programming.I have explained the intuition for dynamic programming solution and have also explained the algorithm using proper examples.I have also shown the code walk through of the bottom-up dynamic programming at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful…CYA 🙂
=================================================================
INSTAGRAM:
LinkedIn:
=================================================================
CODE LINK:
USEFUL PROBLEM:-
Minimum cost path:
Tag: dungeon game, programming interview questions, coding interview questions, programming tutorials, computer science, geeksforgeeks, programming, leetcode, leetcode solution, tech dose, Dungeon Game, Leetcode #174, Minimum cost path, variant of minimum cost path, dp, dynamic programming, bottom up, bottom up dp, bottom up dynamic programming, minimum sum path, dynamic programming interview problem, day 21, june challenge, dp interview question
Xem thêm bài viết về PC: https://sherimoonzombie.net/pc
Nguồn: https://sherimoonzombie.net
I started with 0,0 position
here's my code for the recursion part, its in python.
Some explanation dp is None initialised matrix, r=0.c=0 for first call to solve.
def solve(self, dungeon, r, c, dp):
# if we off the limits of the dungeon
if r >= len(dungeon) or c >= len(dungeon[0]):
return float('inf')
# if we reach the queen
if r == len(dungeon)-1 and c == len(dungeon[0])-1:
dp[r][c] = 0 if dungeon[r][c] > 0 else abs(dungeon[r][c])
return dp[r][c]
# cache the value of right and down
if not dp[r+1][c]:
dp[r+1][c] = self.solve(dungeon, r+1, c, dp)
if not dp[r][c+1]:
dp[r][c+1] = self.solve(dungeon, r, c+1, dp)
curr = dungeon[r][c]
mini = min(dp[r+1][c], dp[r][c+1])
if curr > 0:
if curr >= mini:
a=0
else:
a=mini-curr
else:
a = abs(curr)+mini
dp[r][c] = a
return dp[r][c]
Be sure to add +1 to the returned value of the main call
sir can we take dp[n][n][3] to store the current best, the best and heath need in a single box??
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m=dungeon.size();
int n=dungeon[0].size();
vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
dp[m-1][n]=1;
dp[m][n-1]=1;
for(int i=m-1;i>=0;i–){
for(int j=n-1;j>=0;j–){
int val=min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
dp[i][j]=max(1,val);
}
}
return dp[0][0];
}
};
sir as we know we can easily trace the path also which requires minimum health can we do it like after we trace that path and look for the minimum of all dp[i][j] belonging to that path?? that mnimum abs(min(dp[i][j] + 1)) will be the answer…. i am a bit tired to implement this but this won't be too hard. please reply
Nice explanation , the thing we can avoid this much if else by padding -infinity .Here is my java code.
public int calculateMinimumHP(ArrayList<ArrayList<Integer>> A) {
int n = A.size();
int m = A.get(0).size();
int[][] dp = new int[n+1][m+1];
for (int i=n;i>=0;i–)dp[i][m] = Integer.MIN_VALUE;
for (int j=m;j>=0;j–)dp[n][j] = Integer.MIN_VALUE;
dp[n-1][m]=0;
for (int i=n-1;i>=0;i–){
for (int j=n-1;j>=0;j–){
int k = Math.max(dp[i+1][j],dp[i][j+1])+A.get(i).get(j);
dp[i][j] = k>0?0:k;
}
}
return Math.abs(dp[0][0])+1;
}
I've been breaking my head for hours trying to solve this by top down approach.. Now, I understand why bottom up is a better choice.. When we come top down, we will have to store two values at each cell, the amount of negative energy so far (i.e., initial energy required) and, the amount of positive energy so far (i.e., the energy gained from power up cells).. Now, at a given cell, its hard to decide from which cell we need to come there.. do I have to reach that cell from a cell that has less negative energy(but no positive energy which might be needed later on) or from a cell which has more positive energy (coz, that can be used later on)..
I was stuck there.. Now, this bottom up approach has made things easier.. Now, I don't even need to store the positive energy information coz, it can't be used at the above cells.. it can be be used only by the cells that we visit before it.. Ahhhh, such a nice one it is..!! Made things simpler..!!
Awesome..!!
Is there any top down approach of filling table sir?
Hello Sir,I have a doubt regarding one problem,I'm not sure if that can be done by DP.
The question is similar to minimum cost path but instead of going from (0,0) to(n,n),we can go from any point of first column to any point of last column ((x,0)->(y,n))!Allowed moves are:up,down,right
can u please suggest how can I approach this problem?
Why can't it be done in top down approach? How can we know whether we should we start from last cell or the first?
What would DFS implementation be like?
This person is Angle!
i'm waiting for the day when you will explain egg drop problem,and all set of question related to matrix chain multiplication approach
Why do you start from row-1, col-1? Is it possible do the bottom up from 0,0 cell? If yes, can you tell me how it is possible. I tried from 0,0 cell but I can't.
Sir i didnt understand Why you are taking maximum of right and down
Excellent explanation
Very nice explanation. Thank you! 🙂
Sir, I have one doubt regarding dp
I searched on the internet I got one answer which says there is two way to perform dp one is memoization and other is tabulation. I saw many videos of dp questions where people solve it using tabulation and call it dp. In the memoization, we perform recursion and then try to store the value of the repeating structure in a ds so this is also called dp or not?
can this be soved with top down?
Thanks, awesome explanation 🙂
Trick to set positive numbers to zero was impossible for me to think, and not very easy to understand for me. But you have explained in a very clear and detailed way(your usual way). Please keep continue posting these videos.
I tried starting from 0,0 following the same approach of min-cost path and finally returning abs(dp[m-1][n-1)+1). Could you please explain why it is failing and what things to change in that method?
Honestly speaking sir, your videos are best when it comes to crisp and to the point explanation!
Moreover you always tend to explain multiple approaches and explain which one works the best!
It would be really helpful if you could bring out tutorials for graphs and DP since there aren't many channels making videos on these topics and they are a bit difficult for the beginners as well!
Thank you for the help once again:)
Java Solution
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row=dungeon.length;
int col=dungeon[0].length;
int [][]dp=new int[row][col];
for(int i=row-1;i>=0;i–)
{
for(int j=col-1;j>=0;j–)
{
if(i==row-1 && j==col-1)
dp[i][j]=Math.min(0,dungeon[i][j]);
else if(i==row-1)
dp[i][j]=Math.min(0,dungeon[i][j]+dp[i][j+1]);
else if(j==col-1)
dp[i][j]=Math.min(0,dungeon[i][j]+dp[i+1][j]);
else
dp[i][j]=Math.min(0,dungeon[i][j]+Math.max(dp[i][j+1],dp[i+1][j]));
}
}
return 1+Math.abs(dp[0][0]);
}
}
sir what if i start start filling dp table from (0,0) and at the end return my abs(dp[n-1][m-1])+1. basically i want to say that dp[i][j] should contain minimum value to start from (0,0) and end at (i,j). I have tried this but my approach is not working.
I also used the same approach, but I started with 0,0 position instead of last position, great explanation 😃
Is your solution working for the given input "[[-3,5]]" ?