Dungeon Game | LeetCode 174 | Dynamic Programming | C++, Java, Python
Vložit
- čas přidán 20. 06. 2020
- LeetCode Solutions: • LeetCode Solutions | L...
June LeetCoding Challenge: • Playlist
May LeetCoding Challenge: • Playlist
Github Link: github.com/KnowledgeCenterYou...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
June LeetCoding Challenge | Problem 21 | Dungeon Game | 21 June,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Dungeon Game,
Dungeon Game c++,
Dungeon Game Java,
Dungeon Game python,
Dungeon Game solution,
174. Dungeon Game,
#Facebook #CodingInterview #LeetCode #JuneLeetCodingChallenge #Google #Amazon #DungeonGame #DynamicProgramming
Just by watching your video till 7:51 minutes I am able to solve this question(There was some problem with my base case).Thanks a lot.
Great 👍
Just about to give up my trails and I got the notification. I totally loved it. Thank you
Great.
The first time I thought about dp but I tried start from (0,0), I didnt find an answer so I dropped it. Then I did a recursive function to try all the possible paths. It worked. I use another function with binary search to find candidates and get the answer. I got a lot of time exceed. It was amazing that you found a way using dp but starting from the end. That made sense. I guess I need to learn to try different approaches. I never though it could be possible to use dp starting from the end.
Yes.
sir why the approach of starting from (0,0) and maintaining min health required to reach index(i,j) not working here??plz reply sir would be great help . i am bit confused regarding this.
When you start from (0,0) and go to its neighboring cells, their values will not be final. Bcz May be (0,1) and (1,0) both are positive, so requirement will be small. But, all cells where you csn go from (0,1) and (1,0) like (0,2), (1,1) and (2,0) are large negative values like -15.. Then you will need to go back and correct values for cells which you visited. So, you can use recursive approach here starting from (0,0) and use memoization to prevent re-solving fo cells. Ultimately that recursion will end at last cell(Base case), and then propagate up.
@@KnowledgeCenter thank u so much sir this helped alot.
Glad to hear.
Superb. I couldn't solve it earlier. Now I feel I can.
Happy to help
If we start from (0,0), by checking how much health we require till the current cell, and taking the total positive values till here, then will it work ?
When you start from (0,0) and go to its neighboring cells, their values will not be final. Bcz May be (0,1) and (1,0) both are positive, so requirement will be small. But, all cells where you csn go from (0,1) and (1,0) like (0,2), (1,1) and (2,0) are large negative values like -15.. Then you will need to go back and correct values for cells which you visited. So, you can use recursive approach here starting from (0,0) and use memoization to prevent re-solving fo cells. Ultimately that recursion will end at last cell(Base case), and then propagate up.
why can't we use top -down approach please explain?
Thanks for the video. Can you please also provide a recursive solution,even if its just a rough solution, before going for DP? I think that might help a lot.
func minHealth(i,j){
if(i == r-1 AND j = c-1)
return dungeon[r-1][c-1] > 0 ? 1 : 1 - dungeon[r-1][c-1]
if (i == r-1)
return max(minHealth(i, j+1) - dungeon[i, j], 1);
if (j = c-1)
return max(minHealth(i+1, j) - dungeon[i, j], 1);
return max( min( minHealth(i+1, j), minHealth(i, j+1) ) - dungeon[i,j], 1);
}
call minHealth(0, 0).
It will call minHealth(1,0) and minHealth(0,1) recursively.
So, it will start from (0,0) and terminate at (r-1, c-1).
The recursive Call and DP solution are in Sync. In video we saw that, minHealth requirement for cell (i, j) was dependent on Right and Bottom Cells i.e., (i+1, j) and (i, j+1). And we picked min of these requirements.
So, from this logic recursion follows, and DP tries to mimic it, and get rid of repeated solutions.
thanks for this great video, cleared all my concept
Glad it helped!
Very nice explanation..Thanks for making this video :)
Thanks.
thankyaa!!
Welcome
Thanks for the explanation. Can u plz demonstrate the N Queen problem.
thanks finally got it
Great.
Thank you
Welcome!
you are hero
Haha. Thanks.
You gotta explain in more details what you do and what exactly value/cell you are calculating.
Please continue making leetcode daily challenges video
Ok. Will try. At least for today's challenge I have created one.
Excellent
Thanks
amzing effort
Thanks a lot.
I tried to solve it using top-down DP approach. But it gave me WA for few test cases.
Did it work?
My idea was based on min path sum approach, I first solved it on paper on test cases of my own. It thought it would work fine so I coded it but then it gave me Wrong Answer for few test cases. Solution by my approach was coming different then expected. My idea was basically when we move bottom or right if health goes
Top down means starting from (0,0).
When you start from (0,0) and go to its neighboring cells, their values will not be final. Bcz May be (0,1) and (1,0) both are positive, so requirement will be small. But, all cells where you csn go from (0,1) and (1,0) like (0,2), (1,1) and (2,0) are large negative values like -15.. Then you will need to go back and correct values for cells which you visited. So, you can use recursive approach here starting from (0,0) and use memoization to prevent re-solving fo cells. Ultimately that recursion will end at last cell(Base case), and then propagate up.
@@KnowledgeCenter I got your point, but my implementation was like: that in each cell of the dp table I was storing a pair the first part of pair tells what is the health of Knight at this cell and second part tells what is the min required health to reach at that cell. Suppose value at cell (1,0) is {10,5} and value at cell (0,1) is {5,2} so if I have to go to cell (1,1) so I need to compare above two cells, so condition of choosing the right value for current cell was take the minimum of second value of pair but if they are same then choose the max first value of pair. That way I don't think I need to backtrack and change values of earlier filled cells
Ladkiyan feminism feminism chillaati hai...Aaj tk maine ek question nahi dekha jahaan koi lady ne aake prince ko bachaya ho...Yahaan pe bhi Knight ko problems face krni pad rahi hai ...Mario mein bhi bechara mera maaarioo kiitti baaar mara hai..Aisa kyon Aisa kyon..AAAj se ladikiyan hogi top left corner mein aur ladke jonge bottom right corner pe..Bsss TO bsss