Dungeon Game | LeetCode | DFS Solution Explained in Detail

Google Interview Question. I explain the DFS solution in detail for 174. Dungeon Game LeetCode problem, along with an iterative DP solution as bonus :)
Writeup (Summary + Code):
chaudhary1337.com/dungeon-gam...
Problem:
leetcode.com/problems/dungeon...
==================================================
References:
leetcode.com/problems/dungeon...
leetcode.com/problems/dungeon...
==================================================
Timestamps:
to be added :P
0:00 Discussion
2:34 Observations
5:43 1. Evaluating a path
7:55 2. Enumerating all the paths
9:14 Code in Python3
14:04 Bonus!
==================================================
Follow:
LeetCode: leetcode.com/chaudhary1337/
GitHub: github.com/chaudhary1337
LinkedIn: / tanishq-chaudhary-a203...
My Website: chaudhary1337.github.io/
#LeetCode #LeetCodeDaily #chaudhary1337

[@prashlovessamosa]

Thank you bahiya awesome

[@hoyinli7462]

you saved my time again. a big THX to you!

[@theghostwhowalk]

Thanks for get another amazing video… Curious why solution with LRU cache DFS is much slower than DP. When we use LRU cache, aren’t we effectively eliminating reevaluating overlapping sub problems?

[@chaudharycodes]

Great question!
Both are theoretically solving the same problem, in the same way but with different approaches. Iterative solutions work faster generally, because:
- they are easier for the compiler to optimize
- recursion uses stacks, which costs overheads
If you want to dive deeper, the discussions here should prove fruitful: codeforces.com/blog/entry/44356

[@theghostwhowalk]

@@chaudharycodes awesome thanks!

[@45_ritiksharma32]

I encountered a test case where grid =[[100]] and the expected answer is 1. Why this ?