21 Longest common subsequence Top down DP
Вставка
- Опубліковано 4 лют 2020
- Longest Common Subsequence Problem solution using TOP DOWN APPROACH
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.
Its like you are teaching knapsack all over again! :D
10 am rn
3rd day of watching your series
and Now I'm able to write code myself of some questions without you completely explaining it
Just Superb!!
Same here.
what's the point of mentioning time
@@pranav288 He covered these many videos in 2 days, I think this was the point probably .. but who cares
At 22:07,
minute change is needed, in below condition .....j should be J-1, as below.
t[i][j] = max(t[i-1] [j] , t[i] [j-1]);
Thanks aditya for superb explanation :)
well u r right but he wrote it many times in video so we should get it by ourselves
@@bite091_jamee7 no he wrote so what Abhishek Soni has done write by mentioning this ...thanx aditya
@@sufiyaniqbal5280 as u say
@@bite091_jamee7 bro do u do coding becz i need a coding partner if ur free we can practice together
Bro You are the champ. I haven't seen somebody to explain DP like this. You are doing the great work for the community. Thank you so much. Also, please don't stop making videos, make more content on DSA as everyone should need this kind of explanation.
Thank you very much for this youtube course. I have been rejected at coding interview just because i didn't know how to approach dynamic programming problems. But after practicing it for few months now , I feel confident enough to crack these interviews.
This series is awesome based on recursion and memozied version i was able to get the top down without looking at the video in one shot even though i m a newbie to dp.
salute.
So happy to say that after going through 20 videos, I could code this question even before the 4th minute was hit of this video while simultaneously listening to this video. Thank you Aditya!
us
Else condition should be t[ i ][ j ] = max ( t[ i - 1 ][ j ], t[ i ][ j - 1 ] ) ; U forgot "-1" in second argument of max function.
Yeah, my bad !! Typo !! 😕
@@TheAdityaVerma As the size of the matrix is t[m+1][n+1], shouldn't we return t[m+1][n+1] instead of t[m][n] at last?
@@bijitashyabirinchi1721 when we initialize t[m+1][n+1] the array has index from 0 till m and not till m+1 same case with n. Thus we return t[m][n] and not t[m+1][n+1].
Search for this comment 😅😅...
@@bijitashyabirinchi1721 you first go and learn 2-D array then come to this
You are great teacher. I was very weak at DP but now after watching your videos, I am able to do most of the problems of DP. 😊
Amazing videos seriously! I was able to do the memoized and bottomup code for this by myself because your explanation of the concepts was so good for knapsack itself! :D
after some months you will have way more viewers than any youTube channel on DP !!
thanks bruh!!
I was able to write the correct bottom up version of LCS without even completing the video because I've been watching this playlist from the beginning. All thanks to you Aditya 😀😀
yes i also agree.
After I have seen your KnapSack videos , I didn't even need to see these videos. After understanding the choice diagram , I could do the memoization and tabulation on my own! Thanks to you sir!
Thanks bhaiya, I was really scared of DP, after watching your series in continuation, I am able to write code and solve DP problems easily.
Best teacher for coding problems. Been following your series and has been eye-opening to say the least!! Awesome work Aditya.
Thank you.
Great explanation as usual. Just one information. In the DP array towards the "i" dimension we are only referring to at-most 2 rows at a time [i] and [i-1]. So we can create dp array like dp[2][len2+1]; Then we can use modulo operator to reuse this two rows. Memory optimization only O(min(len1,len2))
Best DP course on internet!
you're explaination of problems are so intuitive that I was able to write code, before you started writing it.
You have explained the concept in a very superb way!! Thanks :)
Solving the problem within 10min but still watch full video dont know why.Thanks buddy its very helpful for us
Greatest explanation of Dynamic Programming!
I want to thank you so so so so so so so so much man!
Amazing videos for beginners!!
You know you're a good teacher, when I know how to do this, before starting the video.
BEST DP series!!!
I never ever thought that I would say this but after @mycodeschool..@AdityaVerma is the next god for CSE students..
sad
Bhai Jeet Gaya Tum!!! OP level teaching!
Hands Down !! Thank You.🙌
I solved it without watching the whole video...I could solve it because I understood really good in Knapsack time. Thank you Adtiya bhai.
Thank you very much.
Sir ,You are just osm ,i wrote Bottom-up(Your Top-Down) Approach without even watching your this video. thanks a lot;)
bhaisaaab maja aagya
bro ur the best,meri recursion sai bahaut fatjati thi but after watching ur recursion playlist +dp vali matlab ab best muje recursion hi lagg raha hai and dp thx alot bro may god bless u and ur family ....aap jesa teacher ho toh banda kahan sai kahan chala jae...
Every time I tried learning DP from any source, used to get confused, and ended up skipping it. With your videos cant stop watching them.. It all makes sense now !! Great going Keep it up!
If DP is an art you are an artist sir
@Aditya Verma Thanks a lot for such a deep insight over these important topics. Please upload more videos on tree and Graphs as well. Thanks
Shat Shat pranam guruji ♥🚀✨
Able to solve without watching videos asn, watched all previous videos so fundas got strong , thanks 🙏
Amazing Explanation.!!
Wow sir you are great teacher i had written my code by myself without watching this video thank you so much bhaiya
Never seen this kind of approach of converting Memoization to Top down ...
awesome !
Thanks !! Will be uploading more videos in may till then keep sharing to help this channel grow + thats motivates me to make more videos !! ❤️✌️
@@TheAdityaVerma sir may is here please upload videos. I am preparing for interview and eagerly waiting for your awesome videos
@@TheAdityaVerma Sir ji august chal rha hai aur videos please daal dijiye, interviews hai samne
@@TheAdityaVerma bro I had a special problem on LCS will you solve it
You should say Memoization to Bottom Up
Explanation is awesome..
Never thought I will learn dp this smooth
Able to solve before watching the video. Thanks a lot Sir
Looking forward for more videos :)
Thank you so much sir🙏❤️
Some videos are awesome, and other are fantaboulus great to see the videos of LCS after knapsack makes it cherry on the cake, thanks dude thanks a lot
usually i dont comment but after watching this playlist ,cant stop commenting
Solve Memoise & Bottom-UP by myself, thanks you sir.
Good Explanation
This series is recursion without memoization repeating the same thing again and again ..... :) btw nice i came here to learn dp and now expert in recursion and dp.
ek dhum masth explanation🔥
What a guy !! Just love your videos ...plz make some videos on other topics too
Mast Bhai,
love from MNNIT
Dil ko sakun mil jata hai ase video dekhne ke bad 3 video dekha mera all doubt clear ho gaya
Thx a lot man!
nice explanation...
ThankYou!!!!
BEST EXPLANATION
I like when he says: " Bas ho gaya bhai, aur kuchh nahi hai isme"
Thankyou sir !
bhaiya i first made the code from by myself then watched it.... thanks to your recursive approach i could make this code by myself..... btw you forgot a -1 at last. thank you bhaiya
Awesome!
Guruji backtracking mein video banaiye plz. Plz, meri request accommodate karein.
please sir backtracking
+1
@@sayantanbanerjee821 +1
+1
Kisi ko mili backtracking ki ultimate playlist jaha se crystal clear ho jae jaise Aditya sir padhate hai
Your are just awesome❤
maza aa gya bhai video se bohot kch sikhne ko mila,
thanks sir 💌💚
boht badiya padhaya maze aagaye
good explanation bro>>>>
Excellent !
bhai tu ne best explain kiya
this dude is fire
halwa bana diya question ko itna asan kaise kar diya bhai,good job bro
thankyou so much sr please make playlist of graph and tree.
happiness is being able to solve the question without even watching the video but i still watch it xD
same :)
Same :)
bro this is bottom up as you also mentioned in a pinned comment in 1st video. Just change the title and description whenever you are free. Video and audio cannot be changed, but title and description can be changed and will avoid confusion for beginners who might come to see your video 1 or 2 years from now once your channel becomes quite big(like abdul bari's channel became big in last couple of years).
true:)
are bhai shab ye kya kr diya aapne . bina video dekhe hi m question solve kr k aa gya .. itne acche se kon smjhata h
Pls change the title to Bottom up -.-
Yeah :)
Yes, in his whole playlist he refers to the Tabulation method as Top-down. It should be Bottom-up. Great work Aditya Verma. I highly recommend everyone to watch this playlist to learn DP.
P.S: Yes, I have watched the whole playlist in a single sitting.
@@Manoj-of8nr
how much time did it take
his title made me double check on my dp concept xD
@@Manoj-of8nr chal jhoota
Please, make a video on finding LCS in O(nlog(n)) time complexity.
bhai aditya bhaiya op saxx bhai saaxxxx just loved ur way of teaching brooo 💓💓
Awsome guru
As Japanese say on leetcode:
Take my knees.
Youu're guru of DSA.
Sir ye to bottom up approach hai kyuki isme apan 0 se upar values daal rahe hain aur pehle wala top down hai na kyuki usme apan n se call karke wo value save kar rahe hain.
And Sir your content is very good. Keep it up, Thank you.
Thank you for this series. Graph ki bhi bnalo
Please make video on backtracking. I will definitely watch ALL your videos till now.
So smooth
please explain to me what is the need for initialization in the bottom-up approach?
Do we have to do bottom up approach in interview mandatorily or just memoisation will work fine?
Great
bhaiya toda lighting acha ho jay tohh mazaa a jaye. Otherwise you r GOD
chaa gya bhai 🐱🏍
Dude!!! DP simple AF
haha Thanks ! 😅✌️
21/50 -> 42% done
Can you solve CONTAINS DUPLICATE I, II, III questions of Leetcode?
Please make videos on backtracking and graph too, please :( .
Yes sir backtraking pls!!!!!!
I think else condition should be like
T[I] [j] = max( t [i-1] [j], t [I] [j-1] )
yea, it's a typo.
Yes
I also observe it and made it correct myself .😊😊
Please make a playlist for Backtracking and Branch-Bound
the recursive+memoisation code on Leetcode is giving TLE as well
yeah, time constraints of dp questions are very strict in leetcode. Even I solve array questions time limit was not that strict you can easily pass brute force solutions there.
my memoisation code got accepted on leetocode.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m=text1.length();
int n=text2.length();
int[][] t=new int[m+1][n+1];
return lcs(text1.toCharArray(),text2.toCharArray(),m,n,t);
}
int lcs( char[] X, char[] Y, int m, int n,int[][] t)
{
if(t[m][n]!=0)
return t[m][n];
if (m == 0 || n == 0)
return 0;
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]=Math.max(lcs(X, Y, m, n-1,t), lcs(X, Y, m-1, n,t));
}
}
Try passing your string by reference. Due to recursive calls by value, it takes some time to create the same string at all function calls. In tabulation there are no recursive calls, therefore it passes.
Plz give dronacharya award to this guy.
this question is is also one of the question which gives tle on solving it using memoization and not tabulation
This is bottom-up approach or also called as tabulation as we start solving from base cases (smaller subproblems) and go towards solving large problem
U r god bro god 🙏🙏