Filling Bookcase Shelves | Recursion Memoization | Why not Greedy | Leetcode 1105 | codestorywithMIK
538Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 97th Video of our Playlist "Dynamic Programming : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good DP based problem : Filling Bookcase Shelves | Recursion Memoization | Why not Greedy | Leetcode 1105 | codestorywithMIK
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 : Minimum Deletions to Make String Balanced | Multiple Approaches | Dry Run | Leetcode 1653 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/filling...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
The approach to solving the problem of placing books on shelves with the minimum height is based on dynamic programming and recursion. Here's a breakdown of the approach:
Dynamic Programming Setup:
A memoization table t is used to store intermediate results to avoid redundant calculations. The table is indexed by the current book index and the remaining width on the current shelf.
Recursive Function solve:
The function solve is defined to determine the minimum height for placing books from the current index onward, given the remaining width on the current shelf and the maximum height of the current shelf.
Base Case: If all books have been processed , return the maximum height of the current shelf (maxHt).
Memoization Check: If the result for the current state (i, remainW) is already computed, return it from the table.
Options: For each book, there are two main options:
Keep the book on the current shelf: If the book fits, recursively calculate the height for the remaining books.
Skip to the next shelf: Place the book on a new shelf and recursively calculate the height for the remaining books.
The result for the current state is the minimum of the two options, which is stored in the memoization table.
Initialization and Execution:
The main function minHeightShelves initializes the class variables and the memoization table, then starts the recursive process with all books unplaced and the full shelf width available.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024