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 RUclips 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 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).
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.
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.
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.
You are the best lecturer I currently found on RUclips 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.
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.
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. :)
It would be helpful if you could explain how you arrive at conclusion of solving a given problem using DP? The thought process and finding DP properties in a given problem.
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]
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!!
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!!
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.
The key to derive the logic is to solve a very small test case yourself and make the matrix by using your brain(without any formula), as test case is small you can use your brain to solve it and populate matrix. Once you have the matrix you have to figure out where does ith value is coming from. On closely analysing the matrix you will figure out how the previous results are being reused. You can now derive a formula for that and write code.
I can't speak for anyone else, but when I'm learning this kind of stuff I usually have some sort of textbook that proves these algorithms mathematically. However, it can get a bit hard to grasp just HOW the algorithm is actually solving it through pure pseudocode or induction alone. So, I usually watch these videos first just to get a basic understanding of the algorithm in action which then helps me better contextualize mathematical/logical learning.
LCS is used to get the distance between the words. We can use this to find K-palindrome too. The key is, use the same string as reverse and find the distance using this also, if zero then they are palindrome if not it will give the distance k to be palindrome. Note as we are using the same string in reverse, dropping the K characters will result in palindrome
I'm here 8 years later! I need him to go through all the Leetcode 75! 😃
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!
Tushar's favorite line - `Yes, we will use dynamic programming to solve this ;)`
please check this playlist : ruclips.net/p/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr
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!
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 RUclips provides.
I'm really thankful to Tushar for making iterative dp my second nature 🙏🏼❤
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 : ruclips.net/p/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr
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!! :)
took only 8 minutes to explain what most take 20+ minutes. And you did it great. cleared up everything. Thanks
One of the Best explanations I have heard so far in coding
All your videos are just awesome. You explain every detail so clearly . I like that you don't rush the things.
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 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).
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 ..
Your way of teaching makes me visualise things and I really want to thank you for this.
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 😀 👏🏻👏🏻
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
Supper clear! After watching your explanation, I am able to finish the code within 5 min! Thank you!
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.
You are an absolute champion, your answer and explanation was really clear great job.
This is the clearest explanation I've seen, thank u so much guy !!!! 🥰
Tushar you are such a good human, thank you a lot
This is the best explanation for LCS problem so far. You are great bro.
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.
Nicely explained and easy to understand . Thanks a lot!
BEST explanation on this topic so far!
Thanks I'm making progress on my interview skills. Awesome tutorials.
+1 for explaining DP in such an easy way. Thanks alot
I must say your videos are very helpful... I consider only your videos for my Data structure and algorithms exams preparation..
You are the best lecturer I currently found on RUclips 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.
2018 Anyone? This is one of the most elegant DP with backtracking table algorithms.
THKS man you just save my Semester
Very clear little tutorial! Nice job and thanks!!
good stuff my guy. question: do we NEED the row and column that's full of zeros?
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 explanation, this makes dynamic programming much easier to understand.
Feels so good to finally understand this, thank you!
great video! saved me hours of trying to understand the slideshow from class!
clear, short explanation. Thank you so much!
Good tutorial. Very articulate and clear 🙏
once again, thank you for your teaching, it is easier to understand, compared to my professor's teaching
After searching LCS a lot on the web, finally I found an easy explanation. Thanks a lot.
What a fantastic lesson! Thank you, Tushar.
You make every topic very easy to understand. Thanks. :)
Excellent Explanation. Thank you Tushar!
i have passed the algorithm subject just by watching your videos... thanks a lot !!
Very good tutorials. Thanks a lot Tushar for the video.
Explained so simply. Thanks a lot.
You have explained all DP problems very well...thanks a ton :)
Great explanation of the process, thanks!
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. :)
Love your videos Tushar ! Thanks ! really appreciate your efforts
Thanks Tushar, you've made it so simple to understand.
Thank you, you really make DP very easy to understand
Very clear and easy to understand.
Cheers !!!
your videos are really helpful and you are doing a noble job.
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 ;)
It would be helpful if you could explain how you arrive at conclusion of solving a given problem using DP? The thought process and finding DP properties in a given problem.
The best explanation on LCS
finally a clear demonstration of LCS
Thank you Tushar, your tutorial are great and helped me a lot!
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]
ive learned alot from your vids of dynamic programming. Thanks man
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!!
Thanks a lot, your videos are really very nice and clear. Helping me a lot in my Algorithm course.....
Thank you for these videos on Dynamic Programming...
yes sir , your explanation process is very good and I'm very easily understand this tricky concepts
thank you very much sir
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
By far the best video on this topic.
You made it look some simple tushar!, you are a great teacher., thanks.
thankyou so much sir ,cant explain the happiness in words
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.
nailed bro .... thanks I was struggling with this problem .. now it is much clear .
great sir, thanks a lot for this tutorial, keep it up 👍👍👍👍🙂🙂
Just remember that once you have a match you cannot match anymore down the row.
Awesome explanation sir. Enjoyed it.
thanks. simply and clearly defined.
why don't you first explain the mathematical logic and then solve the problem?And also how to derive the logic
The key to derive the logic is to solve a very small test case yourself and make the matrix by using your brain(without any formula), as test case is small you can use your brain to solve it and populate matrix. Once you have the matrix you have to figure out where does ith value is coming from. On closely analysing the matrix you will figure out how the previous results are being reused. You can now derive a formula for that and write code.
I can't speak for anyone else, but when I'm learning this kind of stuff I usually have some sort of textbook that proves these algorithms mathematically. However, it can get a bit hard to grasp just HOW the algorithm is actually solving it through pure pseudocode or induction alone. So, I usually watch these videos first just to get a basic understanding of the algorithm in action which then helps me better contextualize mathematical/logical learning.
which textbook you use? i also need to get one.
look for Introduction to Algorithms
"Algorithms unlocked" by Cormen explains the problem and solution logic in beautiful manner. See "Algorithms on String" chapter.
thank you very much you helped me pass algorithms man
Very well explained . Thanks for simplicity!
Thanks!! You have made a really nice tutorial.
LCS is used to get the distance between the words. We can use this to find K-palindrome
too. The key is, use the same string as reverse and find the distance using this also, if zero then they are palindrome if not it will give the distance k to be palindrome. Note as we are using the same string in reverse, dropping the K characters will result in palindrome
It is so clear now after watched this video. Thanks!!
Jesus christ they need to honor this man with a nobel peace prize
Oh my goodness I may just pass the final tmrw. Thank you.
Good explanation. able to understand clearly . thanks a lot
had to watch at 0.75x speed bt understood completely thank you man
Thank you so much for this video, you explained it very well! Much appreciated!
wow you taught better than my professor in my graduate school
Great it's clear lesson,,,,,,,thank you turshar roy
Thanks Tushar, your video lectures help me a lot in studies.So much clearly explained! :)
Thank you very much , keep "walking" with the great content !
Very helpful and easy to understand. Thanks
Thanks alot for this excellent walkthrough.
thanks a lot bro
keep making these types videos
very helpful in clearing concepts
thanks alot for the videos, helps me alot to understand Dp and Network flow.
thanks again
These videos are enjoyable, you rock man