Just wanted to revisit Tushar's videos after completing my employment of 4 years at Google in the Bay Area. big thanks to you Tushar to help me with this and other challenging problems!
The best part about his lectures are that the way he demonstrates things makes our brain automatically figure out why we are doing this and this is what no other channel on TH-cam provides. I'm really thankful to Tushar for making iterative dp my second nature 🙏🏼❤
The video that started my interest in dynamic programming. Seen this video 4 years ago in 2017 for the first time and with one example I got the whole idea about Dynamic programming. After that I'm able to solve most of the coding problems using Dynamic Programming approach.
I wonder how my teachers can explain such simple algorithms in a way that noone understands it. I learned all algorithms from indian students. Thx, I love you man
Thank you Tushar. I am sure that no one have explained Dynamic Programming this simple and straightforward. Even we may not be able understand how the values are filled in the DP array dynamically in other explanations. Most of them are always very simple Fibonacci example or very high level. So, for anyone who would like to understand Dynamic Programming, your videos are the best.
Learning how to use a matrix to solve these kinds of questions was a real break through for me. That visualization is better than seeing code, now I can write it any language easily.
You are the best lecturer I currently found on TH-cam to teach hard problem using Advance Technique. No one else can eplain in short, precise & natural as you Tushar !!! > This will always be your punchline "The best we can do WITHOUT". And it's damn easy to understand in Natural Language rather than cold codes.
thank you very much I was able to understand everything. i was able to see how the already computed values were used for the calculation avoiding the redundancy, which is clearly a dynamic programming concept. thank you for such a wonderful video. Hope you help us more.
I think there needs to be more explanation on why there is a max used when the last char don't match. The reason is explained very well in the following section of the wiki page: en.wikipedia.org/wiki/Longest_common_subsequence_problem#Second_property Suppose that the two sequences X and Y do not end in the same symbol. Then the LCS of X and Y is the longer of the two sequences LCS(Xn,Ym-1) and LCS(Xn-1,Ym). To understand this property, consider the two following sequences : sequence X: ABCDEFG (n elements) sequence Y: BCDGK (m elements) The LCS of these two sequences either ends with a G (the last element of sequence X) or does not. Case 1: the LCS ends with a G Then it cannot end with a K. Thus it does not hurt to remove the K from sequence Y: if K were in the LCS, it would be its last character; as a consequence K is not in the LCS. We can then write: LCS(Xn,Ym) = LCS(Xn, Ym-1). Case 2: the LCS does not end with a G Then it does not hurt to remove the G from the sequence X (for the same reason as above). And then we can write: LCS(Xn,Ym) = LCS(Xn-1, Ym). In any case, the LCS we are looking for is one of LCS(Xn, Ym-1) or LCS(Xn-1, Ym). Those two last LCS are both common subsequences to X and Y. LCS(X,Y) is the longest. Thus its value is the longest sequence of LCS(Xn, Ym-1) and LCS(Xn-1, Ym).
well, i don't know how i could pass quizzes without your videos :( I've been using your videos for most of algorithms and they are ease to understand and not time consuming compared to the time i could spend reading the book and sometime don't even understand the pseudo-code itself. THANK YOU, THANK YOU AND THANK YOU ONCE MORE.
To everyone who is saying that he is NOT explaining the reasoning, please listen closely and pause at 4:50. He explains at 4:50 why we add 1+ diagonal when chars are same and why we do max(left,top) when they are different.
I've been looking at lots of lecture notes, tutorials and videos in the Internet to understand DP, but couldn't clearly understand until I watched your video. Your approach of DP is the best I've ever seen and now I'm confident in DP. :)
its our great teachers in colleges who passed this wealth of memorization knowledge with out giving an explanation like this which makes algorithms difficult to learn. I'm not surprised to hear these comments. I'm glad Tushar is doing such a wonderful job here. Kudos to him!!
Amazing video. Would have taken me an entire day had I gone through online sources. This cleared all the things in less than 10 minutes. Thank you so much!!
Hi Tushar Thank you for your video As for the code: you don't need to create the matrix Here is the code in python: # def longest_common_subseq_(s,t): n=len(s) result=[0]*(n+1) for x in t: row=[0]*(n+1) for j in range(n): if x==s[j]: row[j+1]=result[j]+1 else: row[j+1]=max(row[j],result[j+1]) result=row subseq='' indices=[] for j in range(n): if result[j]
this video has really helped me out for my project. Really thank you. You made it so easy that even a 12yrs old boy would understand this after watching video. Really really thank you again.
thank you so much! I wanted to solve a problem related to this but even seeing the solutions i had no idea what they were doing until i saw your explanation!. will make sure to check more videos of yours. ^_^
Hi Tushar thanks for the videos.. I am going through lot of your material lately... public int lcsDynamic(char str1[],char str2[]){ int temp[][] = new int[str1.length + 1][str2.length + 1]; int max = 0; for(int i=1; i < temp.length; i++){ for(int j=1; j < temp[i].length; j++){ I believe max cases in for loop need to be "i
This is the clearest, complete, and most concise explanation of longest common subseq I've seen so far. Thank you so much!
this is the most sarcastic comment on youtube
Say it again!
I'm here 8 years later! I need him to go through all the Leetcode 75! 😃
Tushar's favorite line - `Yes, we will use dynamic programming to solve this ;)`
please check this playlist : th-cam.com/play/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr.html
haha I always loved that too.
😂😂😂❤
Just wanted to revisit Tushar's videos after completing my employment of 4 years at Google in the Bay Area. big thanks to you Tushar to help me with this and other challenging problems!
reading wikipedia for ages...
finnaly with your video i do understand the sequence so thank you very much:)
greetings from Germany:)
GameKeppers haha, same situation
please check this playlist : th-cam.com/play/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr.html
I still come back to this video years later after tripling my SWE salary, priceless content
The best part about his lectures are that the way he demonstrates things makes our brain automatically figure out why we are doing this and this is what no other channel on TH-cam provides.
I'm really thankful to Tushar for making iterative dp my second nature 🙏🏼❤
took only 8 minutes to explain what most take 20+ minutes. And you did it great. cleared up everything. Thanks
Love, how knowledgeable and clear as a teacher you are. Absolutely in debt. Much respect
Nothing on the net has made DP more easier..thanks a ton!! :)
Superb explanation .. If i am stuck in any problem then instead of google just finding your solution for the problem is the best thing.. Thanks ..
The video that started my interest in dynamic programming. Seen this video 4 years ago in 2017 for the first time and with one example I got the whole idea about Dynamic programming. After that I'm able to solve most of the coding problems using Dynamic Programming approach.
All your videos are just awesome. You explain every detail so clearly . I like that you don't rush the things.
I wonder how my teachers can explain such simple algorithms in a way that noone understands it. I learned all algorithms from indian students. Thx, I love you man
One of the Best explanations I have heard so far in coding
Thank you Tushar. I am sure that no one have explained Dynamic Programming this simple and straightforward. Even we may not be able understand how the values are filled in the DP array dynamically in other explanations. Most of them are always very simple Fibonacci example or very high level. So, for anyone who would like to understand Dynamic Programming, your videos are the best.
This is the best explanation for LCS problem so far. You are great bro.
Learning how to use a matrix to solve these kinds of questions was a real break through for me. That visualization is better than seeing code, now I can write it any language easily.
One of the best explanations I ever saw on this topic !!.... Thank you very much sir 😀 👏🏻👏🏻
Supper clear! After watching your explanation, I am able to finish the code within 5 min! Thank you!
Your way of teaching makes me visualise things and I really want to thank you for this.
You are the best lecturer I currently found on TH-cam to teach hard problem using Advance Technique. No one else can eplain in short, precise & natural as you Tushar !!!
> This will always be your punchline "The best we can do WITHOUT". And it's damn easy to understand in Natural Language rather than cold codes.
You are an absolute champion, your answer and explanation was really clear great job.
I learned most of the stuff from your videos, sir. It's quite helpful.Thank you so much.
thank you very much I was able to understand everything.
i was able to see how the already computed values were used for the calculation avoiding the redundancy, which is clearly a dynamic programming concept.
thank you for such a wonderful video. Hope you help us more.
BEST explanation on this topic so far!
This is the clearest explanation I've seen, thank u so much guy !!!! 🥰
I think there needs to be more explanation on why there is a max used when the last char don't match. The reason is explained very well in the following section of the wiki page:
en.wikipedia.org/wiki/Longest_common_subsequence_problem#Second_property
Suppose that the two sequences X and Y do not end in the same symbol. Then the LCS of X and Y is the longer of the two sequences LCS(Xn,Ym-1) and LCS(Xn-1,Ym).
To understand this property, consider the two following sequences :
sequence X: ABCDEFG (n elements)
sequence Y: BCDGK (m elements)
The LCS of these two sequences either ends with a G (the last element of sequence X) or does not.
Case 1: the LCS ends with a G
Then it cannot end with a K. Thus it does not hurt to remove the K from sequence Y: if K were in the LCS, it would be its last character; as a consequence K is not in the LCS. We can then write: LCS(Xn,Ym) = LCS(Xn, Ym-1).
Case 2: the LCS does not end with a G
Then it does not hurt to remove the G from the sequence X (for the same reason as above). And then we can write: LCS(Xn,Ym) = LCS(Xn-1, Ym).
In any case, the LCS we are looking for is one of LCS(Xn, Ym-1) or LCS(Xn-1, Ym). Those two last LCS are both common subsequences to X and Y. LCS(X,Y) is the longest. Thus its value is the longest sequence of LCS(Xn, Ym-1) and LCS(Xn-1, Ym).
I must say your videos are very helpful... I consider only your videos for my Data structure and algorithms exams preparation..
Tushar you are such a good human, thank you a lot
By far the best video on this topic.
once again, thank you for your teaching, it is easier to understand, compared to my professor's teaching
well, i don't know how i could pass quizzes without your videos :( I've been using your videos for most of algorithms and they are ease to understand and not time consuming compared to the time i could spend reading the book and sometime don't even understand the pseudo-code itself. THANK YOU, THANK YOU AND THANK YOU ONCE MORE.
great video! saved me hours of trying to understand the slideshow from class!
THKS man you just save my Semester
+1 for explaining DP in such an easy way. Thanks alot
To everyone who is saying that he is NOT explaining the reasoning, please listen closely and pause at 4:50. He explains at 4:50 why we add 1+ diagonal when chars are same and why we do max(left,top) when they are different.
Thanks I'm making progress on my interview skills. Awesome tutorials.
Feels so good to finally understand this, thank you!
After searching LCS a lot on the web, finally I found an easy explanation. Thanks a lot.
I've been looking at lots of lecture notes, tutorials and videos in the Internet to understand DP, but couldn't clearly understand until I watched your video. Your approach of DP is the best I've ever seen and now I'm confident in DP. :)
Very clear little tutorial! Nice job and thanks!!
i have passed the algorithm subject just by watching your videos... thanks a lot !!
THANK YOU! You saved me! No one on the net has ever explained DP well but you. Keep it up :)
Nicely explained and easy to understand . Thanks a lot!
your videos are really helpful and you are doing a noble job.
You make every topic very easy to understand. Thanks. :)
Holy mollie! I finally got it!!!! Thanks for the time you put into this.
You have explained all DP problems very well...thanks a ton :)
Thnx a lot... it's so easy to understand and implement and not try to memorize a code When you have Cool teacher like you)) One more time THNX))
do u memorize code generally?
its our great teachers in colleges who passed this wealth of memorization knowledge with out giving an explanation like this which makes algorithms difficult to learn. I'm not surprised to hear these comments. I'm glad Tushar is doing such a wonderful job here. Kudos to him!!
Rudolf Eremyan is this algorithm o(n)?
O(nm)
MILTON KUMAR exactly! And that is not linear time
These videos are enjoyable, you rock man
such a clear explanation. you nailed it
2018 Anyone? This is one of the most elegant DP with backtracking table algorithms.
Amazing video. Would have taken me an entire day had I gone through online sources. This cleared all the things in less than 10 minutes. Thank you so much!!
ive learned alot from your vids of dynamic programming. Thanks man
Great explanation, this makes dynamic programming much easier to understand.
What a fantastic lesson! Thank you, Tushar.
Dude, I really like your videos. Super helpful during prep. I hope you're having fun at your workplace but you should consider doing this fulltime ;)
Perfect tutorial! You deserve hundred of likes for saving my time 👍🏼
Love your videos Tushar ! Thanks ! really appreciate your efforts
Hi Tushar
Thank you for your video
As for the code: you don't need to create the matrix
Here is the code in python:
#
def longest_common_subseq_(s,t):
n=len(s)
result=[0]*(n+1)
for x in t:
row=[0]*(n+1)
for j in range(n):
if x==s[j]:
row[j+1]=result[j]+1
else:
row[j+1]=max(row[j],result[j+1])
result=row
subseq=''
indices=[]
for j in range(n):
if result[j]
Explained so simply. Thanks a lot.
clear, short explanation. Thank you so much!
Very clear and easy to understand.
Cheers !!!
this is the one who helped me thank you sir
Good tutorial. Very articulate and clear 🙏
The best explanation on LCS
Very nice...!! Got it in 8min !! Wonderful work dude!! :)
Thank you, you really make DP very easy to understand
Thanks Tushar, you've made it so simple to understand.
Great explanation of the process, thanks!
You made it look some simple tushar!, you are a great teacher., thanks.
thank you very much you helped me pass algorithms man
Thank you so much for this video, you explained it very well! Much appreciated!
yes sir , your explanation process is very good and I'm very easily understand this tricky concepts
thank you very much sir
Thanks Tushar, your video lectures help me a lot in studies.So much clearly explained! :)
the best explanation ever, thank you
Thanks a lot, your videos are really very nice and clear. Helping me a lot in my Algorithm course.....
It is so clear now after watched this video. Thanks!!
Very good tutorials. Thanks a lot Tushar for the video.
good stuff my guy. question: do we NEED the row and column that's full of zeros?
Excellent Explanation. Thank you Tushar!
you are too good in explaining problems :)
I meant both :). Too good. Keep up the good work.
nailed bro .... thanks I was struggling with this problem .. now it is much clear .
Just remember that once you have a match you cannot match anymore down the row.
thanks a lot, that's the explanation I was looking for
Thank you guy. I've just understood how to solve this problem from you :)
thanks. simply and clearly defined.
Thank you Tushar, your tutorial are great and helped me a lot!
thanks a lot bro
keep making these types videos
very helpful in clearing concepts
this video has really helped me out for my project. Really thank you. You made it so easy that even a 12yrs old boy would understand this after watching video. Really really thank you again.
Clear and to the point! Thanks a ton!
Thank you very much , keep "walking" with the great content !
thank you so much! I wanted to solve a problem related to this but even seeing the solutions i had no idea what they were doing until i saw your explanation!. will make sure to check more videos of yours. ^_^
Thank you once again for the explanation! You really are a life-saver!
had to watch at 0.75x speed bt understood completely thank you man
Thank you for these videos on Dynamic Programming...
Hi Tushar thanks for the videos.. I am going through lot of your material lately...
public int lcsDynamic(char str1[],char str2[]){
int temp[][] = new int[str1.length + 1][str2.length + 1];
int max = 0;
for(int i=1; i < temp.length; i++){
for(int j=1; j < temp[i].length; j++){
I believe max cases in for loop need to be "i
thankyou so much sir ,cant explain the happiness in words
Very well explained . Thanks for simplicity!