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.
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 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 .
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
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?
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)
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.
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.
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 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 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.
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
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?
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.
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.
![กิโลเมตรที่ 0 เดินทางรอบโลกไม่ใช้เครื่องบิน [Around The World Ep. 1]](http://i.ytimg.com/vi/toJG9oofLFY/mqdefault.jpg)
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🔥🔥
☺️
Your SOLUTION is just like a HEAD SHOT to the PROBLEM,eliminated the problem in one way..GREAT MAN,..
😂
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
thanxx for the imp observation part . It was great help
👍🏼
You always give the best and simple explanation whatever be the level of question.....Thankyou soo much
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
Amazing work sir, giving so many videos for free on youtube is a major dent on online ed tech vultures
😅
The way you solved this question is awesome
Thanks :)
Your explanation made this problem very simple. Thank you :)
Welcome :)
Excellent bro. You are a inspirational coder!!
Thanks
I wish to understand the problem like you.
You will :)
what an explaination dude !
Thanks :)
Nice explanation your videos are really good...please keep on making such videos.
Sure 😊
I was doing it with bfs and getting tle, thanks for the explanation
Welcome
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
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?
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 😅
Brilliant Explanation
Can we solve this problem using top-down approach instead of bottom-approach?
Very nice explanation. Thank you! :)
Welcome :)
Excellent explanation
Thanks :)
awesome sir.
Thanks :)
I want to know if the game allows 4 directions to move, how to solve that?
Woohhhoo That is just amazing ...Great
:)
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.
i'm waiting for the day when you will explain egg drop problem,and all set of question related to matrix chain multiplication approach
😅
Can you do the exact same thing top-down?
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.
Thanks, awesome explanation :)
Welcome :)
Was Waiting for today's upload
:)
this question was asked in Uber coding round
😃
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 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.
can this be soved with top down?
can I say this is just a problem of finding minimum positive sum for reaching to the bottom-right cell
excellent
I love this challenge 😍
June challenge is putting up good questions.
Bro, binary search method is intuitive
If confidence table is given what to do
Awesome
Thanks :)
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.
i was just about there but i was trying top down
sir can we take dp[n][n][3] to store the current best, the best and heath need in a single box??
Bro do video on
Matrix median
Sure
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👍
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
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?
The dungeon question is somewhat difficult to understand...
Yea right
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.
This person is Angle!
😅
Is there any top down approach of filling table sir?
No
What would DFS implementation be like?
Please read the pinned comment.
Initially you said answer was 11, at the end it is 7
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
wow!!!!!!!!!!!!!!!!!!!
best
bamm! wow!
😅
It's very tough to understand
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.
😅
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
Your codeforces ID?
I never did CP so I don't have anything to share on it. Replied on your question in another thread.
not clearly explained, looks like he is just reading out the words
What kind of logic is that?
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;