im deaf, and i got a hearing aid and i was told to practice hearing through my hearing aid. so i tried hearing with the closed captions on other videos in other channels and they did not make any sense to my brain. but when i tried yours, i could at least understand some of what you are saying. so thank you for giving me a start by enunciating the words properly. *hugs*
I can't thank you more for this video! Most videos out there put a lot of efforts explaining how to solve a dynamic problem with recursion, memoization, bottom-up yadayada... But for me, the most challenging part is figure out what on the earth the problem wants me to do! Your five steps really point out a promising pattern that I can build my own thinking process with. Thank you!
Unlike most of the other DP videos out there, this one goes into both simple (yet non-trivial) and challenging examples, which are way more likely to be seen in an interview setting instead of problems like Fibonacci, which are beaten to death. The animation is great and the use of DAGs for visualization really helps things click. I'm genuinely surprised I haven't seen most other resources explicitly mention this DAG-based way of thinking about DP problems before, because it makes it infinitely easier to identify subproblems and their relationships (which was my main roadblock for getting to a DP solution, and likely is for others as well). Keep up the great work and I'll be sure to support you in the future!
Thanks for the awesome comment and appreciate the support. I totally agree with everything you said. My main motivation was to find problems that I felt were at a level of difficulty where it requires some real problem solving beyond an example like Fibonacci which I feel is so fundamental that it's not even instructive. The best way to learn and understand DP in my experience is to actually go head first into applying the ideas of finding and solving subproblems in scenarios where the subproblems are a little less clear. And yeah about the DAG relationship, I wanted to make sure I brought that up since in a way, all dynamic programming problems are fundamentally DAG problems. This is mostly just my opinion but I don't feel like a discussion on dynamic programming is complete without mentioning the relationship with DAG's. It's just too fundamental to the core of DP.
@@Reducible there is a problem of finding largest area in a histogram ....i did that in a white page using DAG ....it actually worked but now i got stuck at code implementation...can u plz make a video on that problem and solve it using DAG
@@ReducibleTo be fair I think if you have started with Fibo example and kept the rest of the video it would have been even better. In the sense, as Fibo is a very trivial example the concept of DP would have been assimilated first in an easier way. Then you can digest easily the more difficult examples. This applies specially for those who watch you vids but are a little bit older who take time to assimilate things. Like in my case, I haven't done algorithms since uni. But still the video is still helpful and nicely done :)
This is finally making me understand DP and how to solve those problems without overcomplicating them i love how you go from explaining the idea to actually fully explaining some code and not just pseudo code
Yeah, mistakes were made ... I honestly didn't even realize it was so bad until I got several comments about it. Sorry about that -- I overhauled my old setup and have now actually learned about how to get good audio so I'm hoping it's better in the future. My newest video has no such complaints so hopefully it's better and will continue to improve.
I really like how your explain and visualize the problem for us. Really appreciate your work. Looking forward to learning more concepts from your video
This is probably the best video about Dynamic Programming I've seen on TH-cam, it covers everything from idea to code and I usually have struggles reading the math but the animation really helped break down what's going on. Keep it up, would love to see more examples! Would you ever plan to make object oriented programming videos in the future?
Hey Tiffany, thank you for the awesome comment! There are tons of dynamic programming examples so in the future I could see myself making a video on another challenging problem. For OOP, I haven't really thought about that topic -- maybe? My initial thoughts though are that there may not be too many compelling animations for OOP problems since it's more about code design. The video topics that are usually the best are ones where there is some motivating concept and overarching connection like there is with dynamic programming problems. But who knows, maybe there are some interesting problems in that area -- feel free to let me know if you think of any!
@@Reducible I dont much about OOP. but i have recently come across this topic in discrete math known as Group theory. its a part of abstract algebra. There is a book known as visual group theory and professor macauley uses this in a yt playlist as a reference. Would it be possible to make a video on that??? since many people find it difficult to read that book but i am sure with your animation skills etc you can bring the entire 300 pages of content into 20 mins. The visuals and example connecting discrete math and chemistry architecture rubik s cube are already there. Some highly skilled people like you only can combine it for the audience. Hope this idea is a good enough one for you to ponder about. Thanks for your awesome video collection. I think you and the author of visual group theory book share the same objective : promote intuituivity first then rigorousness. Thanks a lot!!!!!
Thank you for this amazing video! Here is some Julia code that corresponds to 7:50 function lis(A) n = length(A) L = fill(1, n) for i in 1:n subproblems = [ L[k] for k in 1:i if A[k] < A[i] ] push!(subproblems, 0) L[i] = 1 + maximum(subproblems) end push!(L, 0) return maximum(L) end
Who knows, this video is horrible and people definitely didn't understand crap. I came up with a solution rather quickly, especially because i have answered a similar problem a few days ago, then he kept talking and talking and talking and soon i found out he is a complete idiot.
Nice video! Btw, to my ears it sounds like your mic is clipping. If it sounds like this, try reducing your mic gain. It will sound quieter, then you can bring the volume back using an audio effect like limiter or compression.
Thanks so much! I like how you 11:13 provide a visualization of the approach and 16:42 go through the implementation. I haven't seen any video describing DP like this!
I was looking for something like this which explains how to solve dynamic programming step by step rather than just solving questions. This video helped me in a better understanding of dynamic programming than ever before.
Amazing Video! Thanks for subtitles, I'm a non native and your pronunciation is perfect and some words I did not knew I could read the subtitles so I could understand your video perfectly, your way of explain things is wonderful!
Great video to refresh the most reliable approach to solving DP problems! (am an engineer in AI industry). One thing to add, is that at 16:03 when checking if boxes[j] can be stacked on box, we can break the for loop once we meet the first boxes[j] that is too big, because we had sorted the list of boxes by the criteria (length). This means that the remaining boxes[j] in the list will all also be too big. This will make it a little bit more efficient :) (though it won't change the time complexity).
Dynamic Programming: the idea of solving a problem by first identifying and solving subproblems, and then bringing these subproblems together to solve the larger problem. 1. Visualize Examples: a common model in DP is the directed acyclic graph (DAG). 2. Find appropriate subproblems: think about the start and the end of a subsequence. 3. Find relationships between subproblems: 1. What subproblems are needed to solve a particular subproblem P? Go back in the DAG. 2. How to use these needed subproblems to solve P? Use the solutions of the subproblems as a partial solution of P. Start coming up with the recurrence relation. 4. Generalize the relationship: 5. Implement by solving subproblems in the right order:
This was super cool! It helped me understand dynamic problems a bit better. I'm guessing it'll still be a lot of work but this is a great start. I went through this video in chunks and spent time thinking about the steps and the problems at hand. Here's to hoping I won't be entirely clueless when practicing dynamic programming on leetcode from now on.
The best thing is that you don't mix up memoization and dynamic programming. It is really very common, not just on TH-cam tutorials, but even in colleges!
I literally love this video. This video is perfect. Everything about this video, the explanation, the animation everything. I cant thank you enough for this.
My solution for the first problem was to organize the data as a tree where you start at the last entry and connect that to all entries which are lower than it and further back and then do that to all the nodes further down. Then, to find the longest path you can effectively just do a depth first search and move through all of the points in the tree until you have the longest path
This same problem i applied to weighted jobs which kind of looks like same and get solved, while i was looking for this problem TH-cam suggested me this 😁😁, thanks a lot 👍
I've developed a couple dynamic programming algorithms on trees and dags. My prof called these 'local functions', as the value at a node only depends on the in-neighbours. (I haven't seen anyone else calling them that though). The interesting features of these are that the running time is easy to determine based on just the computations required at each node, that it can also be applied to undirected graphs if picking an arbitrary root is possible, and by storing the graph in topological order, it's also IO efficient.
directed acylic graphs and dynamic programming wow!!!!! superb !!!! amazing!!!! i was just bogging around this idea in the morning, but i was not close to it. i was seeing papers related to both dynamic programmig and graphs. being a little weak to dp, I came across your video!!!! wow, the key you have presented is::::::THE GRAPH REPRESENTS ALL VALID SOLUTIONS, not every solution. In mind till now i thought remotely that Dp was somehow computing every solution(including invalid ones)!!!! I know I am totally wrong and I am extremely happy that you were there to correct me. Thanks a lot !!! Thank you very much Reducible!!!!!!!!!!!!! Superb awesome and great work!!!! Thank you again!!!!!!
Wow, this video is a gemstone. I’m a CS major graduate and I still benefitted from it. The presentation is so clear I think it helped me to understand it better now than I did in college!!! Huge fan of the 3b1b visuals too. Did he help you set this up? Great job anyways!
Explanation from 8:11 to 8:26 - broke my head. The guy knows what he is talking about, but his explanation is too academic and hard to comprehend for beginners. Will try to come back to this video in another year...
4:08 - I struggled to understand what does "ending at index k" mean. In the example you show a box around first 4 elements, saying that the sequence ends at index 3, which implies (and is later affirmed) that the indices begin with 0. But in the mathematical example in the beginning, you showed that indices begin at 1. Be careful with this sort of mixup - this kind of stuff is what can screw with your brain for way too long and then have you beat yourself up for missing something so simple/obvious. Best to display indices as well as the values (or actually hide the values for the moment of explaining the more abstract mechanism). When working, redundancy is, well, redundant. When learning, it's a life-saver.
This video helped me code the solution in c, the code finally works and I'm so relieved. Thanks a lot, love your other videos a lot as well, first one i watched was the one about recursion and it's a gem !
Thanks for investing a lot of time in making the animation. I think you need to consider your teaching methodology as well, this video makes the topic much harder than it really is.
t1 = [2, 3, 1, 4, 5, 7, 6, 8, 9] def lis(a): l = [[k] for k in range(len(a))]
for i in range(len(a)): subproblems = [l[n] for n in range(i) if a[n] < a[i]] l[i] = max(subproblems, key=lambda x: len(x), default=[]) + l[i]
return [a[i] for i in max(l, key=lambda x: len(x))]
print(lis(t1)) This is how I kept track of the entire subsequence. But I'm guessing an interviewer would probably point out the space complexity of this.
I thought 3b1b started a channel for Computer Science until I heard your voice. Great content. This channel deserves so much more recognition. Thanks! Keep making more videos!! Hope you make more videos on Graph Theory, Backtracking, Recursion, and some of the interesting topics in CS.
2:18 before seeing the 'right' solution, what I did to find it was to find the smallest number on the left and the largest number on the right. It won't work for all sequences but the longest sequence has to at least be in there somewhere.
I really like the way you explained, it's clean and clear, it's much better than any course about DP in computer science class I took. Visualization DP problem as graph and finding sub-problem are great points, I just love it.
Bro, thank you a lot for this video. Dp problems were always a 'pain in the ass' for me, cause i didn't even know how to start solving them. But this video helped me a lot to understand 2 dp problems and gaved me a pipline how to solve this kind of problems! Really appreciate your work, dude, thanks! Btw this was my first your video. Looking forward to study your whole channel)
It seems from the comments that the video has received quite a bit of praise. While the visualizations are top notch, I am concerned about the structure of the material. More precisely, I expect that the omission of computational complexity would severely hurt the otherwise excellent learning material. Omitting complexity leaves an insurmountable gap in creating an understanding of the necessity of dynamic programming. I do understand the desire to simplify the learning material to reach a wider audience, but this topic is already sufficiently involved, and those capable of comprehending it surely would have at least heard about the term. It is really not that much overhead to show the viewer that (1) the naive solution to LIS (picking all possible combinations of sequences and checking if they are valid and longest) requires a lot of operations (exponential in problem size), whereas (2) the proposed algorithm reduces the complexity to quadratic, which is an extreme improvement. Further, it is instructive to discuss why the proposed algorithm happens to be better than the naive one.
These feel like math problems from math competitions back in middleschool, except it is math with computer programming. Fun problems to think about and solve.
Amazing video! This video turned out so good, that I'd like to encourage you to do the voice over again: because your MIC was clipping as the input gain was probably too loud it deserves a crystal clean audio to go along with it!
Greatest explanation on how to deal with DP problems I've ever seen, The new 3Blue1Brown of algorithms. BTW do you have a profile in a competitive programming platform like codeforces?
Thank you for teaching me in 20 minutes what my professor could not explain in 2 hours , please keep making content !
Why are professors so bad at teaching such fundamental concepts. I feel like they should also grind leetcode to get teaching jobs lol
smart != good teaching
im deaf, and i got a hearing aid and i was told to practice hearing through my hearing aid. so i tried hearing with the closed captions on other videos in other channels and they did not make any sense to my brain. but when i tried yours, i could at least understand some of what you are saying. so thank you for giving me a start by enunciating the words properly. *hugs*
I'm deaf, too. The caption and description in video are very clearly. It's a nice channel for me to learn coding.
@@williamchan142 may god bless you all.
Press F to pay respects to all the people out there that chose the wrong subproblem definition during an interview.
ف
F to myself.
Wait? DP problems come up in interviews a lot?
@@thux2828 Yes. FAANG companies love to ask the hardest questions. Typically that means DP, Graph, and Tree algo problems
I can't thank you more for this video! Most videos out there put a lot of efforts explaining how to solve a dynamic problem with recursion, memoization, bottom-up yadayada... But for me, the most challenging part is figure out what on the earth the problem wants me to do! Your five steps really point out a promising pattern that I can build my own thinking process with. Thank you!
This is pure gold, someone please give this guy a medal !
Unlike most of the other DP videos out there, this one goes into both simple (yet non-trivial) and challenging examples, which are way more likely to be seen in an interview setting instead of problems like Fibonacci, which are beaten to death. The animation is great and the use of DAGs for visualization really helps things click. I'm genuinely surprised I haven't seen most other resources explicitly mention this DAG-based way of thinking about DP problems before, because it makes it infinitely easier to identify subproblems and their relationships (which was my main roadblock for getting to a DP solution, and likely is for others as well). Keep up the great work and I'll be sure to support you in the future!
Thanks for the awesome comment and appreciate the support. I totally agree with everything you said. My main motivation was to find problems that I felt were at a level of difficulty where it requires some real problem solving beyond an example like Fibonacci which I feel is so fundamental that it's not even instructive. The best way to learn and understand DP in my experience is to actually go head first into applying the ideas of finding and solving subproblems in scenarios where the subproblems are a little less clear.
And yeah about the DAG relationship, I wanted to make sure I brought that up since in a way, all dynamic programming problems are fundamentally DAG problems. This is mostly just my opinion but I don't feel like a discussion on dynamic programming is complete without mentioning the relationship with DAG's. It's just too fundamental to the core of DP.
@@Reducible there is a problem of finding largest area in a histogram ....i did that in a white page using DAG ....it actually worked but now i got stuck at code implementation...can u plz make a video on that problem and solve it using DAG
@@ReducibleTo be fair I think if you have started with Fibo example and kept the rest of the video it would have been even better. In the sense, as Fibo is a very trivial example the concept of DP would have been assimilated first in an easier way. Then you can digest easily the more difficult examples. This applies specially for those who watch you vids but are a little bit older who take time to assimilate things. Like in my case, I haven't done algorithms since uni. But still the video is still helpful and nicely done :)
I love this method to explain. Good job! You have mixed the math reasoning and the practical implementation in an ordered and logical way.
Visualizing it as a DAG is such a nice new trick up my hat, thanks for this.
This is finally making me understand DP and how to solve those problems without overcomplicating them
i love how you go from explaining the idea to actually fully explaining some code and not just pseudo code
This is such a great channel, but man, you need to invest in a better microphone...
Agreed, he's literally shouting at the mic.
Yeah, mistakes were made ... I honestly didn't even realize it was so bad until I got several comments about it. Sorry about that -- I overhauled my old setup and have now actually learned about how to get good audio so I'm hoping it's better in the future. My newest video has no such complaints so hopefully it's better and will continue to improve.
@@Reducible That's alright, everyone learns as they go. Keep up your good work!
I agree!
@@Reducible i mean your content quality is great, just need a better mic
Let's give this guy a real appreciation for visualisation, animation and clear cut explanation. Probably the best on this topic on TH-cam ❤️
You are an absolute genius. You are a mathematician , a scientist , an artist and a teacher
I took algorithms course 2 years ago, and I didn't understand DP, and just memorized it to pass the exam.
Now I understand it, thanks you bro ❤
You sir, are a wonderful person and I want you to know that you have changed someone's life today.
I really like how your explain and visualize the problem for us. Really appreciate your work. Looking forward to learning more concepts from your video
This is probably the best video about Dynamic Programming I've seen on TH-cam, it covers everything from idea to code and I usually have struggles reading the math but the animation really helped break down what's going on. Keep it up, would love to see more examples! Would you ever plan to make object oriented programming videos in the future?
Hey Tiffany, thank you for the awesome comment! There are tons of dynamic programming examples so in the future I could see myself making a video on another challenging problem. For OOP, I haven't really thought about that topic -- maybe? My initial thoughts though are that there may not be too many compelling animations for OOP problems since it's more about code design. The video topics that are usually the best are ones where there is some motivating concept and overarching connection like there is with dynamic programming problems. But who knows, maybe there are some interesting problems in that area -- feel free to let me know if you think of any!
@@Reducible I dont much about OOP. but i have recently come across this topic in discrete math known as Group theory. its a part of abstract algebra. There is a book known as visual group theory and professor macauley uses this in a yt playlist as a reference. Would it be possible to make a video on that??? since many people find it difficult to read that book but i am sure with your animation skills etc you can bring the entire 300 pages of content into 20 mins. The visuals and example connecting discrete math and chemistry architecture rubik s cube are already there. Some highly skilled people like you only can combine it for the audience. Hope this idea is a good enough one for you to ponder about. Thanks for your awesome video collection. I think you and the author of visual group theory book share the same objective : promote intuituivity first then rigorousness. Thanks a lot!!!!!
You need to watch more then
No it is not, are you a bot? This video is horrible.
@@khadijah9010 why is it horrible, 4 years ago there was no neetcode or anyone else
You're one of the most underrated channel out there. You deserve more and more recognition. Video is great 🙌🙌 I've even recommended it to my friends
One of the best I watched on this topic!
I have never thought to visualize DP as a DAG but it makes so much sense!
The Best part is you made us think through the process and how to break down a problem. Amazing work.
I really like the way you both explain and visualize DP. Especially the visualization part.
Thank you for this video. Using a directed graph as a visual is very helpful, and I don't recall it ever coming up as a strategy in my studies.
Thank you for this amazing video! Here is some Julia code that corresponds to 7:50
function lis(A)
n = length(A)
L = fill(1, n)
for i in 1:n
subproblems = [ L[k] for k in 1:i if A[k] < A[i] ]
push!(subproblems, 0)
L[i] = 1 + maximum(subproblems)
end
push!(L, 0)
return maximum(L)
end
Awesome
Love this video! Really easy to understand and content is professional. Looking forward to more videos from you.
Thank you! ;)
Ага даже я все понимаю)))
Bro, he complicated stuff even more. How is everyone in the comments complimenting him?
Who knows, this video is horrible and people definitely didn't understand crap. I came up with a solution rather quickly, especially because i have answered a similar problem a few days ago, then he kept talking and talking and talking and soon i found out he is a complete idiot.
One of the best computer science explanations on the TH-cam!!
Nice video! Btw, to my ears it sounds like your mic is clipping. If it sounds like this, try reducing your mic gain. It will sound quieter, then you can bring the volume back using an audio effect like limiter or compression.
Wow, you’re gonna blow up dude. These animations are insanely good for learning. Amazing work
Thanks so much! I like how you 11:13 provide a visualization of the approach and 16:42 go through the implementation. I haven't seen any video describing DP like this!
I was looking for something like this which explains how to solve dynamic programming step by step rather than just solving questions. This video helped me in a better understanding of dynamic programming than ever before.
wow this is so good and at the end i did understand most part and all i need is some hands on practise. thanks for the video
Wish I could have found this channel earlier this semester when I started my algorithms and data structures class. This would have helped a ton.
Honestly, dynamic programming is so easy to me. The hard part is recognizing that it is a dynamic programming problem
The code tracing for the box stacking problem was amazing!
Amazing Video! Thanks for subtitles, I'm a non native and your pronunciation is perfect and some words I did not knew I could read the subtitles so I could understand your video perfectly, your way of explain things is wonderful!
Thank you for the video. Really pointed me in the right direction as to how to approach DP.
**A shift in perspective is what sometimes makes solving hard problems approachable **
I don't usually comment on videos but man this is the best explanation for a programming concept that I've ever seen on TH-cam
thank you... you are one of the best teachers in the world
Beautiful video. Never really thought that directed graphs could be this useful in DP!
Thank you, this video really explained what Dynamic Time Warping is actually doing
Great video to refresh the most reliable approach to solving DP problems! (am an engineer in AI industry). One thing to add, is that at 16:03 when checking if boxes[j] can be stacked on box, we can break the for loop once we meet the first boxes[j] that is too big, because we had sorted the list of boxes by the criteria (length). This means that the remaining boxes[j] in the list will all also be too big. This will make it a little bit more efficient :) (though it won't change the time complexity).
What do you mean by too big.
You should also consider length is sorted but not breadth. So we should check every box of Max height.
Dynamic Programming: the idea of solving a problem by first identifying and solving subproblems, and then bringing these subproblems together to solve the larger problem.
1. Visualize Examples: a common model in DP is the directed acyclic graph (DAG).
2. Find appropriate subproblems: think about the start and the end of a subsequence.
3. Find relationships between subproblems:
1. What subproblems are needed to solve a particular subproblem P? Go back in the DAG.
2. How to use these needed subproblems to solve P? Use the solutions of the subproblems as a partial solution of P. Start coming up with the recurrence relation.
4. Generalize the relationship:
5. Implement by solving subproblems in the right order:
This was super cool! It helped me understand dynamic problems a bit better. I'm guessing it'll still be a lot of work but this is a great start. I went through this video in chunks and spent time thinking about the steps and the problems at hand. Here's to hoping I won't be entirely clueless when practicing dynamic programming on leetcode from now on.
Amazing and intuitive explanation. Great work!
Best channel I have ever seen as a dev. So amazing and soothing at explaining concepts.
Your question were so interesting. I loved those problems seriously. Thanks for this video very very much.
The explanation on the thinking process is really good !
Thnx... Didn't get it at first but it helped a lot once I took a breather to think... Studying more than 8h muddles the mind a little...
The best thing is that you don't mix up memoization and dynamic programming. It is really very common, not just on TH-cam tutorials, but even in colleges!
Yeah this is a masterclass in how to teach CS. Great job!
thanks for this video!! i've really been struggling with DP while doing interview prep
I literally love this video. This video is perfect. Everything about this video, the explanation, the animation everything. I cant thank you enough for this.
Thank you for this video. This really helped me unterstanding dynamic programming for an exam which will be in 2 days
I am definitely sharing this video with my friends and so should everyone else!! Thanks for the amazing tutorial.
My solution for the first problem was to organize the data as a tree where you start at the last entry and connect that to all entries which are lower than it and further back and then do that to all the nodes further down. Then, to find the longest path you can effectively just do a depth first search and move through all of the points in the tree until you have the longest path
That’s a brute force method. Not dynamic programming method
This same problem i applied to weighted jobs which kind of looks like same and get solved, while i was looking for this problem TH-cam suggested me this 😁😁, thanks a lot 👍
This is very specific to the problem shown. This cannot be generalized as the common steps for all dynamic programimng problems
I've developed a couple dynamic programming algorithms on trees and dags.
My prof called these 'local functions', as the value at a node only depends on the in-neighbours. (I haven't seen anyone else calling them that though).
The interesting features of these are that the running time is easy to determine based on just the computations required at each node, that it can also be applied to undirected graphs if picking an arbitrary root is possible, and by storing the graph in topological order, it's also IO efficient.
The language of Gods
directed acylic graphs and dynamic programming wow!!!!! superb !!!! amazing!!!!
i was just bogging around this idea in the morning, but i was not close to it. i was seeing papers related to both dynamic programmig and graphs. being a little weak to dp, I came across your video!!!! wow, the key you have presented is::::::THE GRAPH REPRESENTS ALL VALID SOLUTIONS, not every solution. In mind till now i thought remotely that Dp was somehow computing every solution(including invalid ones)!!!! I know I am totally wrong and I am extremely happy that you were there to correct me. Thanks a lot !!! Thank you very much Reducible!!!!!!!!!!!!! Superb awesome and great work!!!! Thank you again!!!!!!
Wow, this video is a gemstone. I’m a CS major graduate and I still benefitted from it. The presentation is so clear I think it helped me to understand it better now than I did in college!!!
Huge fan of the 3b1b visuals too. Did he help you set this up? Great job anyways!
they use the same animation software I'm pretty sure
Its a library called manim! Its pretty easy to get started with.
Explanation from 8:11 to 8:26 - broke my head. The guy knows what he is talking about, but his explanation is too academic and hard to comprehend for beginners. Will try to come back to this video in another year...
Thank you so much for generalizing such a complex problem in such an way that is so easy to understand. Keep up the great work!
Bless your heart lol was looking for someone to explain some intuition behind these magical solutions.
Super sir , it is one of the most understandable explanation of dynamic programming.
best explanantion of this concept and also the most beauiful in any book or video ever!!!!
The DAG bit is fascinating! Thank you!
I’m gonna be honest. I’m pretty good at problem solving. But this was way over my head.
Thank god someone is on the same page as me :")
You deserve infinite amount of likes! Thank you!
TH-cam recommended your channel to me yesterday. I wish I'd found you earlier! Great explanation and illustration!
4:08 - I struggled to understand what does "ending at index k" mean. In the example you show a box around first 4 elements, saying that the sequence ends at index 3, which implies (and is later affirmed) that the indices begin with 0. But in the mathematical example in the beginning, you showed that indices begin at 1.
Be careful with this sort of mixup - this kind of stuff is what can screw with your brain for way too long and then have you beat yourself up for missing something so simple/obvious. Best to display indices as well as the values (or actually hide the values for the moment of explaining the more abstract mechanism). When working, redundancy is, well, redundant. When learning, it's a life-saver.
because LIS[0] = 1, and all the elements of the list is already set to 1, LIS[0] is not required
@@proloycodes what?
The DAG tip is super helpful!
kindly continue making these videos
This video helped me code the solution in c, the code finally works and I'm so relieved.
Thanks a lot, love your other videos a lot as well, first one i watched was the one about recursion and it's a gem !
Thanks for investing a lot of time in making the animation. I think you need to consider your teaching methodology as well, this video makes the topic much harder than it really is.
t1 = [2, 3, 1, 4, 5, 7, 6, 8, 9]
def lis(a):
l = [[k] for k in range(len(a))]
for i in range(len(a)):
subproblems = [l[n] for n in range(i) if a[n] < a[i]]
l[i] = max(subproblems, key=lambda x: len(x), default=[]) + l[i]
return [a[i] for i in max(l, key=lambda x: len(x))]
print(lis(t1))
This is how I kept track of the entire subsequence. But I'm guessing an interviewer would probably point out the space complexity of this.
90K soon !
With your explanation, I actually find the topic interesting now as well!
Great vid!
I thought 3b1b started a channel for Computer Science until I heard your voice. Great content. This channel deserves so much more recognition. Thanks! Keep making more videos!! Hope you make more videos on Graph Theory, Backtracking, Recursion, and some of the interesting topics in CS.
Thanks for the awesome comment. There is some really awesome CS topics that I have in the works for future videos so stay tuned!
@@Reducible Cool, I had subscribed already!
Oh, does it mean he is the same guy who makes 3b1b vedios?
@@shreengul6488no, he assumed that this person is the person behind 3b1b because of the thumbnail of this video.
I've watched one video of this channel and hit subscribed !!!
What an amazing channel.
Thank you so much for a clear and simple explanation.
2:18 before seeing the 'right' solution, what I did to find it was to find the smallest number on the left and the largest number on the right. It won't work for all sequences but the longest sequence has to at least be in there somewhere.
Your videos are much helpful for learning the contents. Please upload more such contents. I recommended it to my friends.
I really like the way you explained, it's clean and clear, it's much better than any course about DP in computer science class I took. Visualization DP problem as graph and finding sub-problem are great points, I just love it.
Great video! Watching with my whole college dorm. 🐍💪✨
Bro, thank you a lot for this video. Dp problems were always a 'pain in the ass' for me, cause i didn't even know how to start solving them. But this video helped me a lot to understand 2 dp problems and gaved me a pipline how to solve this kind of problems! Really appreciate your work, dude, thanks!
Btw this was my first your video. Looking forward to study your whole channel)
It seems from the comments that the video has received quite a bit of praise. While the visualizations are top notch, I am concerned about the structure of the material. More precisely, I expect that the omission of computational complexity would severely hurt the otherwise excellent learning material. Omitting complexity leaves an insurmountable gap in creating an understanding of the necessity of dynamic programming. I do understand the desire to simplify the learning material to reach a wider audience, but this topic is already sufficiently involved, and those capable of comprehending it surely would have at least heard about the term.
It is really not that much overhead to show the viewer that (1) the naive solution to LIS (picking all possible combinations of sequences and checking if they are valid and longest) requires a lot of operations (exponential in problem size), whereas (2) the proposed algorithm reduces the complexity to quadratic, which is an extreme improvement. Further, it is instructive to discuss why the proposed algorithm happens to be better than the naive one.
Wow! The best explanation ever! Love it! Thank You
Could you please make a video for the case when 2 arrays are given. Like Longest Common Subsequence? Your videos are just amazing.
man can you do more videos on dynamic programming , it helps a lot.
I find the explanations and animations extremely clear. Thanks for making this video!
These feel like math problems from math competitions back in middleschool, except it is math with computer programming. Fun problems to think about and solve.
Great video sir! I appreciate the help :)
Amazing video! This video turned out so good, that I'd like to encourage you to do the voice over again: because your MIC was clipping as the input gain was probably too loud it deserves a crystal clean audio to go along with it!
the best video i have seen, thank you so much. I hope you always release excellent video
thank you so so much, this video is absolutely a lifesaver!!!
using the animations in the right way! great explanation
Thankyou
This video blew my mind on how to break down problems! Most informative video on DP. I have seen! Thank you for making this.
This is the best explanation of dp
Loved the video!!!
It really helped me in understanding the subject.
Greatest explanation on how to deal with DP problems I've ever seen, The new 3Blue1Brown of algorithms. BTW do you have a profile in a competitive programming platform like codeforces?
Aahhh, perfect video for quarantine.