Count possible ways to construct buildings | Recursion | Memoization | Bottom UP | GFG POTD
72Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 80th Video on our Dynamic Programming Playlist.
In this video we will try to solve a good and a classic DP problem - Count possible ways to construct buildings
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 : Count possible ways to construct buildings
Company Tags : Payu
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Count%20possible%20ways%20to%20construct%20buildings.cpp
Leetcode Link : https://www.geeksforgeeks.org/problems/count-possible-ways-to-construct-buildings5007/1
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approach Summary-1 Summary : The solve method is a recursive function that uses dynamic programming with memoization to calculate the number of ways to construct the structure with a given length n and a specified status (either space or building). The base case is when n becomes 0, indicating that the construction is complete, and the function returns 1. The function stores previously calculated results in a 2D array t to avoid redundant calculations. The TotalWays method initializes the memoization table t and calls the solve method for the specified length N, both for the status of building and space. It then calculates the total number of ways by summing the results and returns the square of this total modulo M.
Approach Summary-2 Summary : The initialization sets the base case for i = 0, where there is only one way to arrange buildings and spaces, either placing a building or leaving it as a space. The nested loops iterate over positions (i) and statuses (j), updating the number of ways based on the previous positions and statuses. If the status is "building," the number of ways is determined by the previous position with "space" status. Otherwise, the number of ways is the sum of the ways with both "space" and "building" statuses. The final result is calculated by summing the number of ways at the last position with both "building" and "space" statuses. The result is then squared and returned, applying modular arithmetic with the constant M = 1e9 + 7 to handle large values and prevent integer overflow.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ 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 #2024 #newyear