Dungeon Game | Dynamic programming | Leetcode
Vložit
- čas přidán 20. 06. 2020
- 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: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL PROBLEM:-
Minimum cost path: • Minimum path sum | Min...
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
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.
Keep supporting and i will keep posting useful content :)
That logic of taking 0 instead of cumulative sum was just awesome🔥🔥
☺️
You always give the best and simple explanation whatever be the level of question.....Thankyou soo much
It's not possible to build the table from top left to bottom down.
This is because, in order to compute dp[i][j], you will need to make sure of two things:
your dp[i][j]+dungeon[i][j] should be >0
your dp[i][j]+dungeon[i][j] should be large enough, so that it will be sufficient to cover the minimum requirement on dp for the next step, be it right or down (take whichever requires smaller DP).
So you see, because of the second requirement, your calculation of dp[i][j] will depend on later steps that you could take. This is why you have to know these later steps ahead of time, thus calculating from the bottom right.
reference from leetcode 174 comment section.
leetcode.com/problems/dungeon-game/discuss/52784/Who-can-explain-why-u201cfrom-the-bottom-right-corner-to-left-top.u201d
Your SOLUTION is just like a HEAD SHOT to the PROBLEM,eliminated the problem in one way..GREAT MAN,..
😂
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?
Your efforts to make us understand this problem are commendable . Your an excellent teacher . Keep making videos . Cause their are a few extraordinary people like @myCodeSchool . They give us false hopes . Please never ever stop making videos .
Thanks
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?
sir can we take dp[n][n][3] to store the current best, the best and heath need in a single box??
Can we solve this problem using top-down approach instead of bottom-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.
I want to know if the game allows 4 directions to move, how to solve that?
Your explanation made this problem very simple. Thank you :)
Welcome :)
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
can this be soved with top down?
Amazing work sir, giving so many videos for free on youtube is a major dent on online ed tech vultures
😅
Excellent bro. You are a inspirational coder!!
Thanks
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.
Same here :(
I have the same doubt..but unable to find the answer.
Very nice explanation. Thank you! :)
Welcome :)
what an explaination dude !
Thanks :)
The way you solved this question is awesome
Thanks :)
Woohhhoo That is just amazing ...Great
:)
Brilliant Explanation
I did it first with DFS and Heap. I got time around 250 ms (python3) and there were many solutions for time around 70-80 ms. So I peeked into one and saw dp table. Then solved with DP and got good time. DP solution was easy to code once I solved it in notebook. First solution was quite long (I wrote Heap class, didnt use lib)
I was too thinking about solving it by heap but at the end did with DP
Nice :) I started with DP itself. Knew it was min cost path sum 😅
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?
Yes both are dp. In the recursion method as well we use table to store repeating subproblems. So in both case we are using table and hence both can be called dp.
@@techdose4u Thank you sir👍
Thanks, awesome explanation :)
Welcome :)
Was Waiting for today's upload
:)
Can you do the exact same thing top-down?
Is your solution working for the given input "[[-3,5]]" ?
Yes. DP table will have 0 in place of 6 and -3 in place of -3. So energy required will be 4.
thanxx for the imp observation part . It was great help
👍🏼
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?
This is due the criteria for filling 0 from wherever you can reach the princess. We can't change the position of princess while filling the DP table. Just give it a thought and you will get it.
I also used the same approach, but I started with 0,0 position instead of last position, great explanation 😃
Some people have confusion in TOP-DOWN approach. If you can share your CODE then it will help everyone :)
Sudhanshu Kumar Can you tell me your approach?
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
@@techdose4u added it in the comment
@@MahirHasancse21 added it in the comment
Great great explanation Surya! Thanks a lot. May I just ask why we can't fill the cell from left up to right bottom,, what is the intuition behind this?
I had explained that one of the community post. See the date of this video release and scroll down in my community post section of channel. You will find it. I had told you this on a video call. You remeber?
can I say this is just a problem of finding minimum positive sum for reaching to the bottom-right cell
If confidence table is given what to do
Nice explanation your videos are really good...please keep on making such videos.
Sure 😊
i'm waiting for the day when you will explain egg drop problem,and all set of question related to matrix chain multiplication approach
😅
this question was asked in Uber coding round
😃
I was doing it with bfs and getting tle, thanks for the explanation
Welcome
Excellent explanation
Thanks :)
excellent
I love this challenge 😍
June challenge is putting up good questions.
I wish to understand the problem like you.
You will :)
Is there any top down approach of filling table sir?
No
awesome sir.
Thanks :)
i was just about there but i was trying top down
Awesome
Thanks :)
bamm! wow!
😅
Bro do video on
Matrix median
Sure
wow!!!!!!!!!!!!!!!!!!!
Sir i didnt understand Why you are taking maximum of right and down
Because you want to take the minimum the minimum energy route. More the negative energy required for a path, more will be the cost. So, we take max if two path values which will give us the path with minimum required energy. Maximum of two negative values will give the one more closer to 0.
Initially you said answer was 11, at the end it is 7
best
It was so confusing reading the question on Leetcode, it says if the sum goes below 0, the knight dies and the value starts from negative
This person is Angle!
😅
Bro, binary search method is intuitive
The dungeon question is somewhat difficult to understand...
Yea right
What would DFS implementation be like?
Please read the pinned comment.
Your codeforces ID?
I never did CP so I don't have anything to share on it. Replied on your question in another thread.
It's very tough to understand
Hey is this recursive logic correct ??
int helper(vector &A,int i,int j,int n,int m,int power,int ans){
if(i>=n || j>=m){
return INT_MAX;
}
if(i==n-1 && j==m-1){
power=power+A[i][j];
if(power
What kind of logic is that?
Your code is too easy to understand and we can build a logic after understanding it, but the explanation is really bad in the video. Too long video and literally I skipped to the code and understood why it is working.
😅
not clearly explained, looks like he is just reading out the words
why this code of you is getting failed.
int r=dungeon.size();
int c=dungeon[0].size();
if(r==1 && c==1 && dungeon[0][0]>0)return 1;
vectordp(r,vector(c));
for(int i=r-1;i>=0;i--){
for(int j=c-1;j>=0;j--){
if(i==r-1 && j==c-1){
dp[i][j]=dungeon[i][j];
}
else if(i==r-1){
dp[i][j]=min(0,dp[i][j+1]+dungeon[i][j]);
}
else if(j==c-1){
dp[i][j]=min(0,dp[i+1][j]+dungeon[i][j]);
}
else{
dp[i][j]=min(0,dungeon[i][j]+max(dp[i+1][j],dp[i][j+1]));
}
}
}
return abs(dp[0][0])+1;