Dungeon Game | Brute Force | Recursion | Memo | Bottom Up | Leetcode 174 | DP On Grids | MIK
95iPad PDF NOTES - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad PDF Notes/Dungeon Game - Leetcode 174.pdf
Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 34th Video of our Playlist "DP Concepts & Qns" by codestorywithMIK
We already covered the introduction of DP On Grids in video-29 and video-30 of this playlist.
Video-29 - Part-1 - • Introduction | DP On Grids | Part 1 |...
Video-30 - Part-2 - • Introduction | DP On Grids | Part 2 |...
Today we will be solving a very good problem based on Grid DP - Dungeon Game | Brute Force | Recursion | Memo | Bottom Up | Leetcode 174 | DP On Grids | codestorywithMIK
We will solve it first using Brute Force Approach and then Recursion and Memoization and then we will convert that to Bottom Up.
I will explain the reason behind everything which needs to be known for clearly understanding the solution. It might be a lengthy video,
but for beginners I have added minute details which made it lengthy.
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Dungeon Game | Brute Force | Recursion | Memo | Bottom Up | Leetcode 174 | DP On Grids | codestorywithMIK
Company Tags : will update later
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/DP on Grids/Dungeon Game.cpp
Leetcode Link : https://leetcode.com/problems/dungeon-game/
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Segment Tree Concepts Playlist : • Segment Tree | Introduction | Basics ...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Video Summary :
Approach 1 - Brute Force (Binary Search on Answer) with Memoization
This approach uses binary search on the initial health value, with a recursive DFS to check if the knight can survive from the top-left to the bottom-right of the dungeon. Memoization is applied to store the results of previously computed states, but this approach can lead to TLE (Time Limit Exceeded) due to the high number of possible health values and states.
Approach 2 - Recursion and Memoization
This approach uses recursive DFS to explore all possible paths to the bottom-right corner. It uses memoization to store the minimum health required for each state (cell) to avoid redundant calculations. This solution is efficient with O(m*n) time complexity and works within the problem's constraints.
Approach 3 - Bottom-Up Dynamic Programming
In this approach, the solution is computed iteratively using a bottom-up DP technique, starting from the bottom-right corner and working towards the top-left corner. This approach ensures we always have the required values (down and right) available when filling the table. It is efficient with a time complexity of O(m*n) and avoids recursion, making it both space and time efficient compared to the recursive approach.
✨ Timelines✨
00:00 - Introduction
0:12 - Motivation
0:35 - Problem Explanation
6:15 - Brute Force + Better Using Binary Search On Answer
10:20 - Coding Brute Force + Time Complexity
21:27 - Recursion & Memoization + Tree Diagram
26:45 - Most Important Part
34:03 - Small example to understand important part
56:27 - Coding Recursion & Memoization
1:02:17 - Understanding Bottom Up
1:07:02 - Converting Recursion Memo to Bottom Up
1:12:36 - Coding bottom up
#MIK #mik #Mik
#coding #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodequestions #leetcodechallenge #hindi #india #easyexplaination #interview #interviewpreparation #github #google #video #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #codinginterview #interviewprep #technicalinterview #interviewquestions #codingchallenges #interviewready #dsa #india #helpajobseeker #mik #MIK