Dp 25. Longest Common Subsequence | Top Down | Bottom-Up | Space Optimised | DP on Strings

a

In this video, we solve the LCS Dp, this is the first problem on the pattern Strings on DP.

[pratyakshsinha]

Understood and you've completely changed my life. Doesn't matter if I get placed in a good company or not but the quality of this lectures are supreme and I will carry this knowledge for rest of my life.

[manthenanagendra]

putting your years of hardwork in some videos, how lucky we are, Thanks a lot striver bhaiya for everything you are doing for us

[arjundevmishra]

Protect this guy at all costs. Thank you sir for all your hard work in making this video.

[anweshabanerjee]

If someone is following Striver's series then this LCS is also a cakewalk..#Striver gives u confidence and you are no longer scared of dp😁

[kartiksuman]

understood bhaiya!!! after a very long time i am back to your channel....previously i was doing a race that as soon as you upload the video, i should watch it then n there, before the next video gets uploaded in this dp series, but due to some busy schedule, i lost the race. yeah, but your quality and energy is still the same as your starting videos

[arteigen]

In the future, Mr. Vikramaditya will go down as the G.O.A.T online DSA teacher.

[duyhuynh]

You're a great teacher. If possible, please do problems about DP on tree. I struggle with them. Thank you!

[donno]

I used to be scared of Dp when I started coding journey, but when I am actually doing it, it's cake walk. Thankyou striver for sharing your knowledge.

[Amitchoudhary-ijwe]

I am very grateful to you for uploading this playlist. This is
Understood.

[kanikajain]

This was life-changing. Thank you Striver, you taught what paid courses could not for so many years. I wish I had discovered your site earlier; it would have saved so much time and energy.

[avimandavia]

No other video on the topic will offer you a better explanation than this! This is just pure teaching excellence! Subscribed.

[sujalgupta]

46:05 for space optimization we don't require the loop for prev as the values are already zero in it.

[ramanahlawat]

What an explanation, absolutely brilliant. I am starting to love coding now. Thanks

[akashyadagouda]

Its taking while to digest this information for me,
Just imagine the efforts this guy is adding to make it available for everyone.

[mjmusic]

absolutely minds bogling.i am not kidding i wasn't able to solve simple recusion questions few weeks ago now i can solve medium and hard dp questions on my own without watching videos.all i can say thank you striver.

[ankita]

understood, always in awe of you genius and hard working you are:)

[arunkumarsahoo]

15:34 "You kow i am hearing you" in the background

[siddharthsarraf]

for those who don' t want to use shifting of index in tabulation, they can do it in traditional way using below code. we can discuss if you have any doubts.

int text1, string text2) {
int n1= text1.size();
int n2= text2.size();
vector<vector<int>> dp(n1, vector<int>(n2, -1));

//filling first coloumn of the matrix
//say we have text1= bcade and text2=a then
//the longest cmmn subsqnce is 0 until index1 reaches 2, once it reaches 2 beyond that lcs =1;


for(int i=0; i<n1; i++){
if(text1[i]==text2[0]){
dp[i][0]=1;
i++;
//once we find text[i]==text2[0] then we initialize all cells after that cell in first coloumn to 1

while(i<n1){
dp[i][0]=1;
i++;
}
break;
}
else
dp[i][0]=0;

}
//same thing we do for first row
for(int j=0; j<n2; j++){
if(text1[0]==text2[j]){
dp[0][j]=1;

j++;
while(j<n2){
dp[0][j]=1;
j++;
}
break;
}
else
dp[0][j]=0;

}

// now just converting recursive code into tabulation

for(int i=1; i<n1;i++)
{
for(int j=1; j<n2; j++){
if(text1[i]==text2[j]){
dp[i][j]= 1+dp[i-1][j-1];
}
else{
dp[ i ][ j ]= max(dp[ i-1 ][ j ], dp[ i ][ j-1 ]);
}
}
}
return dp[n1-1][n2-1];
}

[deadlockgaming]

you are a god level teacher🙇‍♂🙇‍♂🙇‍♂
never thought dp would be so easy

[VishalYadav-gkkg]

Very nice explanation sir, Thank you!