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 UA-cam provides. I'm really thankful to Tushar for making iterative dp my second nature 🙏🏼❤
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
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.
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.
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 the best lecturer I currently found on UA-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.
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'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. :)
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.
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]
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!!
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.
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 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
How do we know whether to move left or up, after we filled in the matrix and are back tracking. I'm getting really lost at that part because for the example I'm using with two strings A,B,C,B,D,A,B and B,D,C,A,B,A.
I like your videos and the explanation. Good job! For this specific video, I found it hard to understand the logic.Here is what I suggest you could do as you are a great programmer and teacher. Explain why it is a DP problem instead of directly saying that it is a DP problem. Explain the approach or recursion. Remaining things, you are anyways doing pretty great. Thanks for your videos.
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.
yeah i have read many people complaining about this guys lectures cause tushar dont explain recursive approach and this guy dont explain the problem approach and blaming his teachings, dude this is dynamic programming series, first go and learn how to code in recursion, and then practice basic dp programs which u can find in gfg and then come here, then you cant stop praising this person's efforts very clean peice of code...
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!
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!
Tushar's favorite line - `Yes, we will use dynamic programming to solve this ;)`
please check this playlist : ua-cam.com/play/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr.html
haha I always loved that too.
😂😂😂❤
I still come back to this video years later after tripling my SWE salary, priceless content
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 : ua-cam.com/play/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr.html
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 UA-cam provides.
I'm really thankful to Tushar for making iterative dp my second nature 🙏🏼❤
Nothing on the net has made DP more easier..thanks a ton!! :)
Love, how knowledgeable and clear as a teacher you are. Absolutely in debt. Much respect
took only 8 minutes to explain what most take 20+ minutes. And you did it great. cleared up everything. Thanks
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
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.
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.
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.
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 ..
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.
You are the best lecturer I currently found on UA-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.
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).
Supper clear! After watching your explanation, I am able to finish the code within 5 min! Thank you!
THKS man you just save my Semester
This is the best explanation for LCS problem so far. You are great bro.
Your way of teaching makes me visualise things and I really want to thank you for this.
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.
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. :)
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.
2018 Anyone? This is one of the most elegant DP with backtracking table algorithms.
One of the best explanations I ever saw on this topic !!.... Thank you very much sir 😀 👏🏻👏🏻
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.
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]
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
This is the clearest explanation I've seen, thank u so much guy !!!! 🥰
BEST explanation on this topic so far!
i have passed the algorithm subject just by watching your videos... thanks a lot !!
Tushar you are such a good human, thank you a lot
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.
After searching LCS a lot on the web, finally I found an easy explanation. Thanks a lot.
great video! saved me hours of trying to understand the slideshow from class!
Thanks I'm making progress on my interview skills. Awesome tutorials.
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!!
Feels so good to finally understand this, thank you!
I must say your videos are very helpful... I consider only your videos for my Data structure and algorithms exams preparation..
Nicely explained and easy to understand . Thanks a lot!
THANK YOU! You saved me! No one on the net has ever explained DP well but you. Keep it up :)
You have explained all DP problems very well...thanks a ton :)
good stuff my guy. question: do we NEED the row and column that's full of zeros?
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 ;)
By far the best video on this topic.
What a fantastic lesson! Thank you, Tushar.
once again, thank you for your teaching, it is easier to understand, compared to my professor's teaching
Great explanation, this makes dynamic programming much easier to understand.
+1 for explaining DP in such an easy way. Thanks alot
such a clear explanation. you nailed it
Very clear little tutorial! Nice job and thanks!!
Holy mollie! I finally got it!!!! Thanks for the time you put into this.
Perfect tutorial! You deserve hundred of likes for saving my time 👍🏼
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 best reference! :) Thank you very much.
Thank you so much for this video, you explained it very well! Much appreciated!
your videos are really helpful and you are doing a noble job.
ive learned alot from your vids of dynamic programming. Thanks man
These videos are enjoyable, you rock man
You make every topic very easy to understand. Thanks. :)
The best explanation on LCS
can anyone plz explain why are we taking maximum of top and left when characters are not matching?
had to watch at 0.75x speed bt understood completely thank you man
clear, short explanation. Thank you so much!
Thank you very much , keep "walking" with the great content !
You made it look some simple tushar!, you are a great teacher., thanks.
Thanks Tushar, you've made it so simple to understand.
Love your videos Tushar ! Thanks ! really appreciate your efforts
yes sir , your explanation process is very good and I'm very easily understand this tricky concepts
thank you very much sir
Good tutorial. Very articulate and clear 🙏
thank you very much you helped me pass algorithms man
Very good tutorials. Thanks a lot Tushar for the video.
Explained so simply. Thanks a lot.
Thank you, you really make DP very easy to understand
Thank you once again for the explanation! You really are a life-saver!
Great explanation of the process, thanks!
How do we know whether to move left or up, after we filled in the matrix and are back tracking. I'm getting really lost at that part because for the example I'm using with two strings A,B,C,B,D,A,B and B,D,C,A,B,A.
Excellent Explanation. Thank you Tushar!
finally a clear demonstration of LCS
Very clear and easy to understand.
Cheers !!!
Your explanation is very good.
Just sometimes, I feel you go too fast . But apart from that its helping me a lot in interview prep.
Thanks a lot!!
+Tushar Roy Sure. I do that a lot.
Just remember that once you have a match you cannot match anymore down the row.
Thank you for these videos on Dynamic Programming...
Great video, really helped my understanding. I find it quite difficult to see what algorithms are actually doing just by looking at wikipedia.
I like your videos and the explanation. Good job!
For this specific video, I found it hard to understand the logic.Here is what I suggest you could do as you are a great programmer and teacher.
Explain why it is a DP problem instead of directly saying that it is a DP problem.
Explain the approach or recursion.
Remaining things, you are anyways doing pretty great.
Thanks for your videos.
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.
yeah i have read many people complaining about this guys lectures cause tushar dont explain recursive approach and this guy dont explain the problem approach and blaming his teachings, dude this is dynamic programming series, first go and learn how to code in recursion, and then practice basic dp programs which u can find in gfg and then come here, then you cant stop praising this person's efforts very clean peice of code...
Best video to describe the LCS
wow you taught better than my professor in my graduate school
Thank you guy. I've just understood how to solve this problem from you :)
Very well explained . Thanks for simplicity!
this is the one who helped me thank you sir
Oh my goodness I may just pass the final tmrw. Thank you.
Very nice...!! Got it in 8min !! Wonderful work dude!! :)
Concise and well explained, didn't really understand this algo too well in DP
Cheers!
Jesus christ they need to honor this man with a nobel peace prize