20 Longest common subsequence Memoization
Вставка
- Опубліковано 4 лют 2020
- 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.geeksforgeeks.org/longest...
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.
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!
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
Beautiful explanation
Thanks buddy!!
@@tanmayshishodia1507 Name doesn't matter bhai , approches samajh me aa gyi naa
defination to khi se bhi padh skte ho
you are correct, I was looking for this comment.
Aap toh prepbytes, coding blocks, coding ninja, etc ki business kharap kr doge... Thanks😍
prepbytes don't need others for that !!
@@aakashyadav6228 lol
@@aakashyadav6228 why?
You are legend! I could do it myself because u explained it so well in knapsack videos! Thanks a ton!
Thanks palak !! Keep watching and Sharing !!
same here
+1
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..:)
Exactly, First time I had to skip to the code part in his videos!!!
20 of 50 (40%) done! Starting from 4:05 for the next couple of minutes is a gem on recursion!
love ur dedication
following you bro..
If you get TLE for memoization then pass arguments by referrence
thanks bro.
Wow. Thanks dude. I was worried that something is wrong in my code.
Thanks dude!!! Was so confused why my code was giving TLE.
thanks :)
Duniya me abhi bhi ache log baaki hai 😭😭
Best playlist for dynamic programming. Hope reaches to every student. Thanks Aditya..!
Thanks brother, Do subscribe and share, that keeps me motivated to do more !!
Aditya Verma's DP playlist with 2X speed........It's way satisfying than anything!! ❤️❤️
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.
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!
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.
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
same
really worthy watching ur tutorials.. pls make more tutorials on algorithms ... thank you
Thank you, I will
Knapsack explanation was so great that I could write this code myself !
hands down the best playlist for dynamic programming
You are the only one on youtube who made recursion , DP easy for students.....
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 :)
Same here :)
same here
Dude great work .
I recommend this course to many of my friends
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 ...
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.
yesss
Yes, you are right, I actually has mentioned that in the pinned comment of the very first video.
@@TheAdityaVerma apologies haven't seen that. Thanks for your great videos. Keep them coming.
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
Ab pata chala ki kese recursion se memories and top down approach find karte hee...
Great explanation bro
ur knapsack video was too good, which lead to make this problems easier to understand. Thanks.
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.
I understnad multiple approach , Now i would say if i complete all your videos i will crack somewhere I always rejected at this datastructure.
All I can say is that :- you have earned yourself a subscriber ( and a fan) kudos to your efforts and way of teaching 🎉
sir your way of teaching is so great thanks alot for making dp so easy
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.
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.
This is the best playlist on Dp anywhere on the internet
Your way of explaining is grt, Can you pls also share some video on problems based on Binary Tree, Prims Algorithm, shortest path etc..
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!
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!!
how was your placement?
@@coldfinger3472 Very Good actually. Got placed as SDE in MTX Group with 52 Lakh CTC.
bhai thanks, bohot jagah dhundha , ye global matrix problem de rha tha. yaha sb clear ho gya!!! aage bhi yaad rhega
Best DP course on internet!
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.
Thank you bhai. you're doing great work. please make a playlist on graph and tree also.
🙇🏻♂️ Thankyou so much.
🍁 Legend of DP Aditya Verma 🔥.
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 ❤️.
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
}
}
I like it Man Can't believe how some one can explain by this way
Smae bhaiya, I too loves eriting "Recursion and the meomization" it looks really cool to me, and it gives clean code as well.
Another great video!! Thank you soooo much
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.
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?
Thanks aditya verma sir...dp genius
Really great explanation. But Bottom up approach is not memorization technique, it's Tabulation. It created confusion.
very nice explaination...mind blowing bhaiya..keep it up❤❤
Pen ghuma ke purani yadein taza kar di bhai.. btw brilliant explaination!
We can't get better than this.❤❤
I got tle using memoization approach but it works in top down approach🙂🙂
Just pass the strings by reference
@@darshangupta3804 thanks bro. it worked!!!
@@darshangupta3804 any particular reason as to why passing strings by reference works in this case?
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
Apart from DP explanations pen rotation is awesome.😄
great explanation.
No one else teaches DP better than you. Best wishes !
You are wrong, striver taught better than him
great work and series by you bro
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😂.
We can initialise 2d array by double pointer also like
int** dp = new int*[n+1];
for(int i=0;i
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.
One word- Legend of DP
Could someone advise me on whether I should learn dynamic programming from Striver or Aditya Verma? Which one is better?
Really nice Playlist
Excellent Explanation
great channel for studying dp 👌
Please make more video on dsa , by watching ur video I am able to understand and solve ques on leetcode .
This guy is FAAAAADDDDD Insan... Hats Off !!! MEri taraf se 21 topo ki salami.
Can anyone please explain what is the use of static when we declare the array for memorization globally?
excellent explanation
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!!!
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.
Thanks!🙌
Thank you for existing................
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 ..
Because that never gets called. We never call t[0][0]. Because when m=0 and n=0, the base condition returns 0.
Thanks it's help a lot !!
one of favourite teacher after abdul bari
Brilliant thanks!
swad aa gaya bhai❤️
You are great 👌👌👌
@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?
bro mera leetcode pe TLE ara h
what a way to teach 🤗🤗🤗
Chalo apan agla lecture ka code karte hain... GOD of DP Aditya Verma
legend aditya verma
Thank you sir!
You are amazing!!!!
Wow bhaiya kya padhate ho yaar aap
Sach me bohot acha samjhate ho
amazing sirji
Can we put recursive calls on Threads ?
Tum bhout mast kaaam krta h aditya bhai.
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
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.
Sir, aap aur videos laayiye na ... aap bahut accha samjhaate hain ... kai din ho gaye aapke videos nahi aaye
Mind Blowing
Aditya Verma Why can't we store 0 in the matrix while initilaizing?
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
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 !!
can anyone help me how to fill 2d array with -1 in global scope in java? like what he does using mimset in cpp
Thankuuuu Sir ❤️❤️❤️🥳🥳🥳🥳😍
Is there a memory efficient method for memoization...
2d array takes a lot of memory for large inputs....
well i guess you can create a HashMap and so on. does the same thing and we can fetch data in O(1) complexity
You are legend!
thanks sir....💥💖
tabahi macha diye bhai
bhai TLE de rha hai ye memoized code gfg me, aisa kyu ??
Thank u bhai
Is it possible to declare a static 2D array in Java? I tried searching online but couldn't find much. Or I'll have to pass it in the method call? That's the only way?
yes it is