20 Longest common subsequence Memoization

Longest Common Subsequence Problem solution using Memoization
Given two sequences, find the length of longest subsequence present in both of them.
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.
PROBLEM STATEMENT LINK:www.geeksforge....
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻‍💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻‍♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.

[@rashmikiranpandit8962]

Anyone who is getting confused with Top-down and bottom up, Recursion memoization is always TOP-DOWN(and not bottom up), as we take a bigger problem and recusively solve for the smaller subproblems. Whereas in tabular DP where we start filling the table from top left to bottom right is actually BOTTOM-UP because we compute dp values of smaller subproblems first and then using these values compute dp value of bigger problems. PS: Top down and Bottom up is decided by the essence of methodology and not by whether we are filling table from top to bottom or vice versa!

[@tanmayshishodia1507]

Yuppp you are right, he got confused between the two terms and in the whole series he called memoization as bottom-up and tabulation as top-down lol

[@kakadiazeel]

Beautiful explanation

[@anilsinghnegi1481]

Thanks buddy!!

[@tekbssync5727]

@@tanmayshishodia1507 Name doesn't matter bhai , approches samajh me aa gyi naa defination to khi se bhi padh skte ho

[@MrRavi20khatri]

you are correct, I was looking for this comment.

[@palakmanocha6509]

You are legend! I could do it myself because u explained it so well in knapsack videos! Thanks a ton!

[@TheAdityaVerma]

Thanks palak !! Keep watching and Sharing !!

[@abhishekmore5856]

same here

[@akshatw7866]

+1

[@suchitragiri4546]

Yes me too... I also solved bottom up as well as top down just after understood the logic behind it!! that's I was looking for..:)

[@saumitrashukla8969]

Exactly, First time I had to skip to the code part in his videos!!!

[@vivekanandapradhan9067]

Aap toh prepbytes, coding blocks, coding ninja, etc ki business kharap kr doge... Thanks😍

[@aakashyadav6228]

prepbytes don't need others for that !!

[@anandsharma5850]

@@aakashyadav6228 lol

[@ashu3128]

@@aakashyadav6228 why?

[@0anant0]

20 of 50 (40%) done! Starting from 4:05 for the next couple of minutes is a gem on recursion!

[@Unknown-Stranger]

love ur dedication

[@arnabmukherjee5840]

following you bro..

[@harshagarwal7552]

Best playlist for dynamic programming. Hope reaches to every student. Thanks Aditya..!

[@TheAdityaVerma]

Thanks brother, Do subscribe and share, that keeps me motivated to do more !!

[@sairamakurti4808]

If you get TLE for memoization then pass arguments by referrence

[@BEEMohdArbazAli]

thanks bro.

[@sanjayvasnani988]

Wow. Thanks dude. I was worried that something is wrong in my code.

[@prernagupta243]

Thanks dude!!! Was so confused why my code was giving TLE.

[@ashishkatyal]

thanks :)

[@amandeepnokhwal2977]

Duniya me abhi bhi ache log baaki hai 😭😭

[@adityakhandelwal7925]

I studied your knapsack videos so dedicatedly that as you were explaining longest substring problem, I was able to visualize the choice diagram by myself and the recursion code. Once you wrote the recursion code, I immediately went to geeksforgeeks and tried to solve the problem using top down DP and bang on!!! It successfully passed in 1st attempt. Thanks a Lot :)

[@aditisaxena9097]

Same here :)

[@shivamdwivedi3534]

same here

[@VishalGupta-uu5eb]

same here :)

[@adarshverma013]

you removed the fear of dp i had from me, i did the tabulation while watching memoization video, really awesome work sir!!!!!! Thanks a Lot

[@adityajoshi3922]

same

[@nitinbaghel1073]

Aditya Verma's DP playlist with 2X speed........It's way satisfying than anything!! ❤️❤️

[@nightmare_9]

really worthy watching ur tutorials.. pls make more tutorials on algorithms ... thank you

[@TheAdityaVerma]

Thank you, I will

[@TheVijaySaravana]

Bhai, youtube pe saare videos dekha iss topic mein. Koi bhi itna clear se explain na kiya! Iss topic ke upar aapka jo clarity hai vo isme dikha raha hai.. Hats off!

[@piyushsrivastava5824]

Hi, your videos are good. One thing, the 2-D array approach where we start building from base cases are bottom-up (which you call Top-down). Top-down is when you start from problem and keep breaking in smaller ones i.e. recursive plus memoization for optimization.

[@rishabhyadav8269]

yesss

[@TheAdityaVerma]

Yes, you are right, I actually has mentioned that in the pinned comment of the very first video.

[@piyushsrivastava5824]

@@TheAdityaVerma apologies haven't seen that. Thanks for your great videos. Keep them coming.

[@aptitudepointiit-bhu5358]

For those wondering, how to store -1 in the DP array in platforms like gfg, where the main function is not accessible to us ?? I also had the same confusion, but finally came up with this: We can declare the dp[1001][1001] and a boolean flag, globally, i.e., outside all functions and inside the solution Class. Now, initially the flag stores true value, and we will use this in the LCS function like: if(flag==true) { memset(dp, -1, sizeof(dp)); flag = false; } This flag = false ensures that memset is only applied once, so that it can set the dp array with -1 value only once, as we did, using the main function, thus we successfully memoize the code in platforms like GFG. FULL CODE: int dp[1001][1001]; bool flag = true; public: //Function to find the length of longest common subsequence in two strings. int lcs(int x, int y, string s1, string s2) { if(flag) {memset(dp, -1, sizeof(dp)); flag = false;} if(x==0 || y==0) return 0; if(dp[x][y] != -1) return dp[x][y]; if(s1[x-1]==s2[y-1]) return dp[x][y] = (1 + lcs(x-1, y-1, s1, s2)); else { return dp[x][y] = max(lcs(x-1, y, s1, s2), lcs(x, y-1, s1, s2)); } } ALSO, REMEMBER ONE THING, IF YOU ARE PASSING A 2D ARRAY IN FUNCTION, SPECIFY THE BOUNDS OF THE SECOND VARIABLE WHILE ACCEPTING IT. EX: int func(string s1, int dp[][1001]) is the correct way to accept 2D array in any function, whereas, int func(string s1, int dp) is incorrect.

[@jenilshah2231]

you could have just declared a vector of vector with -1 as default value it doesn't need the memset or anything.

[@manasikasande9400]

Knapsack explanation was so great that I could write this code myself !

[@ankurgupta4696]

i already did memoization and top down dp coz i have watched all your knapsack still dont wanna miss your explanations so watching the video

[@mansigoyal4796]

You are the only one on youtube who made recursion , DP easy for students.....

[@Phoenix-pk7uc]

Others teach table filling and you teach DP. From the 8th video I could solve all the problems own my own because of your teaching process. Thank you for making this tutorial.

[@SarangShekokar]

hands down the best playlist for dynamic programming

[@Weeniekri5773]

discovered his channel recently, he is so underrated. Also i love how he concludes every video with the little summary.

[@Anjalikumari-sg1rs]

Best Playlist of dp. You teach in such a way that I could really build up my concepts of dp. You just removed my fear of dp.Looking forward for more such Playlist on backtracking and graph. Please upload videos on these topics also. It would be a great help as placements are starting.

[@rajgothi2633]

Ab pata chala ki kese recursion se memories and top down approach find karte hee... Great explanation bro

[@algorithmicthinker]

Hi Aditya, just a small thing that is revolving in my brain 🧠 that whether memorization is called bottom up DP or top down DP as we start solving our problem from top most state i.e. dp[m][n] and we reach till base state. Please do throw some light on it. Anyways love your work ❤️.

[@racistindian5316]

Guys if someone is getting TLE in gfg by subitting this code in c++ then pass the string by referance so that your code will not create copy of the string. Here is the code in case you need help: int helper(int x,int y,string &s1,string &s2){ if(x==0 || y==0) return 0; if(dp[x][y]!=-1) return dp[x][y]; if(s1[x-1]==s2[y-1]) return dp[x][y] = 1 + helper(x-1,y-1,s1,s2); else{ int op1 = helper(x-1,y,s1,s2); int op2 = helper(x,y-1,s1,s2); return dp[x][y] = max(op1,op2); } }

[@shivanshyadu4830]

Thankyou so much bro it helped❤

[@racistindian5316]

@@shivanshyadu4830 your welcome

[@VikashKumar-uo6bx]

I got tle using memoization approach but it works in top down approach🙂🙂

[@darshangupta3804]

Just pass the strings by reference

[@kshitijbodhankar3668]

@@darshangupta3804 thanks bro. it worked!!!

[@harshalshridharkallurkar4555]

@@darshangupta3804 any particular reason as to why passing strings by reference works in this case?

[@shubhammahindru3563]

Apart from DP explanations pen rotation is awesome.😄

[@adityabhosale8461]

No one else teaches DP better than you. Best wishes !

[@vbp123]

You are wrong, striver taught better than him

[@rishabsinha8749]

We can initialise 2d array by double pointer also like int** dp = new int*[n+1]; for(int i=0;i

[@yashbhanushali8456]

Lekin Kyu. Pointer agar ap lerahe ho, to memory apko free bhi karni padegi. It's c++ and not java garbage collection ni hai yaha. Why to end up in such a big mess.

[@praphulyadav4471]

sir your way of teaching is so great thanks alot for making dp so easy

[@bipul2138]

Bhai badiya video ek baar fir Bas ek chiz, memset use krnge initialize krne ke liye to bas -1 ya 0 kr skte h saare elements ko Aur kisi chiz se initialize krenge to garbage value show krega matrix Better to use 2-D vector Initialization : vector < vector > dp(n+1, vector (m+1, -1) ); Thanks a lot

[@TheAdityaVerma]

Yeah ofc you have only use 0, -1, true , false with memset. And we will always be initializing it with -1 to check if the value if stored or not. So I think we are good. Thanks for watching !!

[@gauravagarwal8592]

Man that this is so simple u make it I read multiple times videos , nothing worked first time i am happy .YOU are the BEST BUDDY. People should call you champion. Now i am more greedy I understand graphs with algorithm but still want you to come up for that.

[@gauravagarwal8592]

I understnad multiple approach , Now i would say if i complete all your videos i will crack somewhere I always rejected at this datastructure.

[@saurabhsen3560]

The way you teach is awesome!!!. You really have made DP easy. Thank you for making such a wonderful video. Can you make a video on LIS ...

[@sukantaghosh3237]

Really great explanation. But Bottom up approach is not memorization technique, it's Tabulation. It created confusion.

[@piyushsarraf4814]

Do every memoized recursion have same time complexity as compared to table form ? @ Aditya Verma And a small correction table will t[m+1][n+1] not the opposite.

[@lifehustlers164]

Well Aditya Sir , On Leetcode other than Scrambled String ,its memoization code also failled to accept (Giving Run time error on test case 46/47), So scrambled String and Longest common Subsequence codes gives stack overflow error in memoization. Till now....,BTW AWESOMMEEE VIDEOS!!!

[@hqz9380]

ur knapsack video was too good, which lead to make this problems easier to understand. Thanks.

[@anuraga3018]

Really nice explaination. @aditya Verma I have followed this and wrote this program. Looks like some issue with memoization concept which i understand from your video :- def longestCommonSubsequence(text1: String, text2: String): Int = { val cache = Array.tabulate(text1.length,text2.length)((r,c) => -1) // Declaring array and filling -1 values, for memoization return helperBug(text1,text1.length-1,text2,text2.length-1,0,cache) } def helperBug(text1:String,i:Int,text2:String,j:Int,soFar:Int,cache:Array[Array[Int]]): Int = { if(i == 0 || j == 0){ soFar } else if(cache(i)(j) != -1) cache(i)(j) else { var max = 0 if(text1(i) == text2(j)) { max = max.max(helperBug(text1,i-1,text2,j-1,soFar+1,cache)) // Instead of 1+ LCS(), I have kept length in parameter = soFar } else { max = max.max(helperBug(text1,i-1,text2,j,soFar,cache)) max = max.max(helperBug(text1,i,text2,j-1,soFar,cache)) } cache(i)(j) = max; max } }

[@cyborg9910]

C++ implementation for the same: #include const int mod=1e9+7; using namespace std; // } Driver Code Ends // function to find longest common subsequence static int dp[1001][1001]; class Solution { public: int test(int x, int y, string &s1, string &s2) { if(x == 0 || y == 0) { return 0; } if(dp[x][y] != -1) { return dp[x][y]; } if(s1[x-1] == s2[y-1]) { return dp[x][y] = 1+test(x-1,y-1,s1,s2); } else { return dp[x][y] = max(test(x-1,y,s1,s2),test(x,y-1,s1,s2)); } } //Function to find the length of longest common subsequence in two strings. int lcs(int x, int y, string s1, string s2) { memset(dp,-1,sizeof(dp)); int p = test(x,y,s1,s2); return p; } }; // { Driver Code Starts. int main() { int t,n,k,x,y; cin>>t; while(t--) { cin>>x>>y; // Take size of both the strings as input string s1,s2; cin>>s1>>s2; // Take both the string as input Solution ob; cout

[@yogeshkumarprajapat8147]

sir, actually ye method jo is video mai hai vo top down approach hai kyunki is approach mai hum tree ke root se niche aate hai(bigger problems ko pehle directly approcah karte hai which get divided into smaller prblms with time) i.e leaves(aapne apne explanation mai vo bataya ), aur jo next video mai hai vo bottom up approach hai kunki usme hum directly smaller problems ko approach karte hai (with the help of loop) fir finally at index [n][m] hamara required result aa jaata hai

[@amitkumar-xt2ms]

bhai thanks, bohot jagah dhundha , ye global matrix problem de rha tha. yaha sb clear ho gya!!! aage bhi yaad rhega

[@AbhishekSingh-jv6uc]

Thanks a lot, brother!! You have made DP so easy and interesting. I have placements after 3 months and I have the confidence I needed after watching your videos. Love you, bro!!

[@coldfinger3472]

how was your placement?

[@AbhishekSingh-jv6uc]

@@coldfinger3472 Very Good actually. Got placed as SDE in MTX Group with 52 Lakh CTC.

[@vladimirputin2756]

public class LCSMemo { // Declare the dp array as a global variable static int[][] dp; // Function to find the length of the Longest Common Subsequence (LCS) public static int lcs(String s1, String s2, int n, int m) { // Base case: If either of the strings is empty, the LCS is 0. if (n == 0 || m == 0) return 0; // If the result for this pair of lengths is already computed, return it. if (dp[n][m] != 0) return dp[n][m]; // If the last characters of both strings match, include them in the LCS. if (s1.charAt(n - 1) == s2.charAt(m - 1)) { // Store the result in the memoization table. dp[n][m] = 1 + lcs(s1, s2, n - 1, m - 1); return dp[n][m]; } else { // If the last characters don't match, consider two cases: // 1. Excluding the last character of s1 and finding LCS with s2. // 2. Excluding the last character of s2 and finding LCS with s1. dp[n][m] = Math.max(lcs(s1, s2, n - 1, m), lcs(s1, s2, n, m - 1)); return dp[n][m]; } } public static void main(String[] args) { String s1 = "abdefjs"; String s2 = "adfs"; int n = s1.length(); int m = s2.length(); // Initialize the dp array with dimensions (n+1) x (m+1) dp = new int[n + 1][m + 1]; // Call the LCS function with the lengths of both strings. int result = lcs(s1, s2, n, m); // Print the length of the LCS. System.out.println("Length of Longest Common Subsequence: " + result); } }

[@prithvirajpatil8150]

Dude great work . I recommend this course to many of my friends

[@JerichoMatt]

All I can say is that :- you have earned yourself a subscriber ( and a fan) kudos to your efforts and way of teaching 🎉

[@swapnilshivpuje3705]

I like it Man Can't believe how some one can explain by this way

[@darshantawte7435]

Can you please update time and space complexity of every code (recursive,memoize,tabulation) on all DP problems in the playlist. Please make a short video for each problem regarding time/space complexities or you can even specify it in the video description.

[@pv2930]

This guy is FAAAAADDDDD Insan... Hats Off !!! MEri taraf se 21 topo ki salami.

[@kuch_visahi_bahi9871]

This is the best playlist on Dp anywhere on the internet

[@aayushpagare9366]

swad aa gaya bhai❤️

[@herculean6748]

Thanks!🙌

[@tanujgyan787]

Awesome explanation man, aise to ye baat sun sun k tum thak gaye hoge coz har koi yahi bol raha but bhai seriously kamal videos banayi hain yaar!

[@ansarishadman]

Pen ghuma ke purani yadein taza kar di bhai.. btw brilliant explaination!

[@AMAR-pc6ht]

Smae bhaiya, I too loves eriting "Recursion and the meomization" it looks really cool to me, and it gives clean code as well.

[@ayushmishra3388]

You teach like the way every programmer should think, just sharing my thoughts in the starting of video, in heading you have mentioned **memoization as bottom-up, but it should be top-down**, coz it uses recursion, correct me if i am wrong bro.

[@sachchidanandsingh57]

Your way of explaining is grt, Can you pls also share some video on problems based on Binary Tree, Prims Algorithm, shortest path etc..

[@pranjalmishra2602]

Bhaiya, Top down = memoization and Bottom up(DP) = for loop Right? : |

[@ayushbisht2689]

No memoization is bottom up .

[@pranjalmishra2602]

@@ayushbisht2689 To be more simple, Memoization uses the top-down approach to solve the problem i.e. it begin with core(main) problem then breaks it into sub-problems and solve these sub-problems similarly. Source - Google

[@ayushbisht2689]

@@pranjalmishra2602 your right bro. My bad

[@mohit84604]

javascript code :- let string = "abcdef" let string1 = "abuiopmnbv" let n = string.length let m = string1.length let dp = new Array(n+1).fill(new Array(m + 1).fill(-1)) function lcs(a, b, n, m,dp) { if(n == 0 || m == 0){ return 0 } if(dp[n][m] != -1){ return dp[n][m] } if(a[n-1] == b[m-1]){ return 1+lcs(a,b,n-1,m-1,dp) }else{ return Math.max(lcs(a,b,n-1,m,dp),lcs(a,b,n,m-1,dp)) } } console.log(lcs(string, string1, n, m,dp))

[@priyarathore9266]

Best DP course on internet!

[@PratapSingh-si7qo]

Bhai I love all your video of dp. Thanks for making my interest in coding. I request you to make video playlist on graph. It looks much complicated.

[@ankitasingh2563]

class Solution { public int longestCommonSubsequence(String text1, String text2) { int n = text1.length(); int m = text2.length(); int[][] t = new int[n + 1][m + 1]; // Initialize the first row and first column with zeros for (int i = 0; i < n+1; i++) { for (int j = 0; j < m+1; j++) { if (i == 0 || j == 0) { t[i][j] = 0; } } } // Fill the t array with LCS values for (int i = 1; i < n+1; i++) { for (int j = 1; j < m+1; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { t[i][j] = 1 + t[i - 1][j - 1]; } else { t[i][j] = Math.max(t[i][j - 1], t[i - 1][j]); } } } return t[n][m]; } } leetcode problem no : 1143

[@anuragshah516]

Aapne itne ache se padhaya knapsack ki iski recursive, memorization aur bottom up code to khud se he likh li maine 🤩. Dp halwa lag rahi hai😂.

[@prathmesh4894]

LEETCODE : 1143. Longest Common Subsequence CODE: class Solution { public: int LCS(string &X,string &Y, int m, int n,int t[][1001]){ if(n==0 || m==0){ return 0; } if(t[m][n] != -1){ return t[m][n]; } if(X[m-1]==Y[n-1]){ return t[m][n] =1+LCS(X,Y,m-1,n-1,t); } else{ return t[m][n] = max(LCS(X,Y,m,n-1,t ),LCS(X,Y,m-1,n,t)); } return -1; } int longestCommonSubsequence(string text1, string text2) { //base condition // agar dono string 0 hai int static t[1001][1001]; memset(t,-1,sizeof(t)); int m = text1.size(); int n = text2.size(); return LCS(text1,text2,m,n ,t); return -1; } };

[@shivanshyadu4830]

Bro can you explain me that why are you returning -1 in LCS & its main function????

[@sharmanihal99]

@@shivanshyadu4830 you can omit this return statement, it is not requires as lcs function will anyway return value.

[@ipsitasahoo8387]

Really nice Playlist

[@karthikkallur727]

Wow bhaiya kya padhate ho yaar aap Sach me bohot acha samjhate ho

[@debanshumajumdar4826]

One suggestion - Please add how to optimize space of a 2d array and how to think to do that. Even in Bottom-Up using Tabulization.

[@suchitragiri4546]

You are great!! but I have one confusion ... is that same logic we apply in top down and bottom up but why the bottom is more faster than the top down, while memory space is same?

[@animeshmishra4282]

🙇🏻‍♂️ Thankyou so much. 🍁 Legend of DP Aditya Verma 🔥.

[@asmitshukla4649]

very nice explaination...mind blowing bhaiya..keep it up❤❤

[@thisthatvlogs5334]

Thank you for existing................

[@tekbssync5727]

bhai TLE de rha hai ye memoized code gfg me, aisa kyu ??

[@shantanukumar4081]

Thank u bhai

[@AnonymousBear-bb8pc]

Could someone advise me on whether I should learn dynamic programming from Striver or Aditya Verma? Which one is better?

[@samyakgoyal2958]

Can anyone please explain what is the use of static when we declare the array for memorization globally?

[@divyanshukumar813]

Another great video!! Thank you soooo much

[@noobichesser9434]

Chalo apan agla lecture ka code karte hain... GOD of DP Aditya Verma

[@blasttrash]

bro you should make videos in English. You have the power to topple entire algo-teaching industry. Like business models of leetcode, algoexpert, intervieweing.io etc. Hell, your videos have the potential to topple interviews in tech industry. After your videos, big tech companies might stop asking dp questions coz everyone will be really good at it. :)

[@swagatdas1991]

@aditya verma, maano ya naa maano, this is true af. Or you can add really good subtitles, as in the introductory video.

[@durgeshsahu.7]

Excellent Explanation

[@hritiksingh1767]

Thanks aditya verma sir...dp genius

[@factoworld9527]

great work and series by you bro

[@devanshrastogi6305]

great explanation.

[@avert_]

I tried the same logic but not all gfg cases are passing: What am i missing out? Here's the python3 code:(ignore the I/O) dp = [[-1 for i in range(101)] for j in range(101)] def lcs(m,n,X,Y): ''' :param m: length of string X :param n: length of string Y :param X: string X :param Y: string Y :return: Integer ''' # code here if m == 0 or n == 0: return 0 if dp[m][n] != -1: return dp[m][n] if X[m-1] == Y[n-1]: dp[m][n] = 1 + lcs(m-1,n-1,X,Y) return dp[m][n] else: dp[m][n] = max(lcs(m-1,n,X,Y),lcs(m,n-1,X,Y)) return dp[m][n]

[@TomJerry-bp9ig]

Bhai pta chle to mujhe bhi btana😓

[@pujakumari6391]

Mind Blowing

[@aviseklahiri3864]

Why did we not initialize the first row and first column with zero like we used to do for knap-sack ? The base condition says us to do so from the recursive forumaltion ..

[@atreyadyaram850]

Because that never gets called. We never call t[0][0]. Because when m=0 and n=0, the base condition returns 0.

[@sharmajikaladka3011]

Thank you bhai. you're doing great work. please make a playlist on graph and tree also.

[@saurabhkanswal7954]

one of favourite teacher after abdul bari

[@ChandraShekhar-by3cd]

Thanks Aditya for such a nice explanation. I had one doubt regarding the time complexity of the memoized version , how the time complexity turns out to be O(n^2) ??????

[@tanaysaraf9402]

two for loops used! recursive calls will be placed in stack and result will be stored , so complexity will become on^2

[@sairamakurti4808]

to be precise T.C = O(n*m) since we are filling every box of the table so it is o(n*m)

[@ChandraShekhar-by3cd]

@@sairamakurti4808 Thanks

[@ccarnagee7867]

Is there a memory efficient method for memoization... 2d array takes a lot of memory for large inputs....

[@ANUABRAHAMCS-A-]

well i guess you can create a HashMap and so on. does the same thing and we can fetch data in O(1) complexity

[@saumyagupta7400]

Hi I have a doubt, hum hamesha array ko 0 se hi kyo start krte hai.

[@ashutoshhans]

As per geeksforgeeks and every where I studied memoization is top down and tabulation is bottom up. Can you please help in clearing the doubt

[@satviksrivastava9504]

haan vo terms thode mixed up h playlist m hai but concept sahi h bilkul

[@ashutoshhans]

@@satviksrivastava9504 Yep totally agree.. concepts are correct and crystal clear

[@rrMaxwell]

i did the memozisation and tabulation on my own yay!!!

[@ankursharma6084]

Memoized version is showing time limit exceeded in both gfg and leetcode. Anyone else facing the same problem.

[@shivanshyadu4830]

bro do you have solution??

[@022_ananyasrivastava8]

Aditya Sir is the god of DP

[@shubhamagarwal352]

@Aditya Verma I tried it with creating an array of size t[n][m] and saving the value in t[n-1][m-1] instead of t[n][m] and it worked fine on leetcode. I did it b'coz I noticed that first row and column is not getting used. Can you please let me know if it is also a right way and may work for other memoization questions?

[@gta6515]

bro mera leetcode pe TLE ara h

[@bite091_jamee7]

amazing sirji

[@sumitkulkarni3950]

ab pata chala actually dp kaha pe use hoti hai. THANKS.

[@shivamtiwari20028]

God Of DP❤

[@hrithikdhanraj2919]

We can't get better than this.❤❤

[@KanishkaDutta]

excellent explanation

[@kamalsingh1345]

Thankuuuu Sir ❤️❤️❤️🥳🥳🥳🥳😍

[@sohinichaudhuri518]

Sir, aap aur videos laayiye na ... aap bahut accha samjhaate hain ... kai din ho gaye aapke videos nahi aaye

[@abhilasharaj7991]

Please make more video on dsa , by watching ur video I am able to understand and solve ques on leetcode .