5 Simple Steps for Solving Dynamic Programming Problems
ฝัง
- เผยแพร่เมื่อ 28 พ.ค. 2024
- In this video, we go over five steps that you can use as a framework to solve dynamic programming problems. You will see how these steps are applied to two specific dynamic programming problems: the longest increasing subsequence problem and optimal box stacking. The five steps in order are as follows:
1. Visualize examples
2. Find an appropriate subproblem
3. Find relationships among subproblems
4. Generalize the relationship
5. Implement by solving subproblems in order
After taking an in depth look at these problems, at the end of the video we will also have a discussion about common subproblems that you may encounter while solving dynamic programming problems.
Error correction: for the box problem, using dictionary solutions only works if we are given unique boxes -- using a list of subproblems would be a better way to solve it if we wanted to handle duplicate boxes (similar to how we did the longest increasing subsequence).
Support: / reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music:
Prelude No. 2 by Chris Zabriskie is licensed under a Creative Commons Attribution license (creativecommons.org/licenses/...)
Source: chriszabriskie.com/preludes/
Artist: chriszabriskie.com/
All other music by Aakash Gandhi
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
Dynamic Programming is so annoying...
Thank you for teaching me in 20 minutes what my professor could not explain in 2 hours , please keep making content !
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
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 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
I love this method to explain. Good job! You have mixed the math reasoning and the practical implementation in an ordered and logical way.
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
Wow, you’re gonna blow up dude. These animations are insanely good for learning. Amazing work
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*
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 :)
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!
Love this video! Really easy to understand and content is professional. Looking forward to more videos from you.
Thank you! ;)
Ага даже я все понимаю)))
The Best part is you made us think through the process and how to break down a problem. Amazing work.
Let's give this guy a real appreciation for visualisation, animation and clear cut explanation. Probably the best on this topic on TH-cam ❤️
Visualizing it as a DAG is such a nice new trick up my hat, thanks for this.
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!
Thank you for all your videos! I particularly struggle with dynamic programming, and a few months ago I started solving a lot more questions, but eventually took a break when I felt I wasn’t really understanding why some of my solutions worked.. Anyway, the DAG representation is new to me, and I’m going to try out some more problems again! Always nice to get a new perspective on things
I am definitely sharing this video with my friends and so should everyone else!! Thanks for the amazing tutorial.
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!
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
Such a great video again. You deserve much more recognition.
I really like the way you both explain and visualize DP. Especially the visualization part.
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.
This is pure gold, someone please give this guy a medal !
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.
This video provides such great clarity about the steps and logic behind formulating a solution. Keep up the good work!
This video is so insightful! Thanks a ton for all the effort!
Looking forward to more :)
Best channel I have ever seen as a dev. So amazing and soothing at explaining concepts.
I have never thought to visualize DP as a DAG but it makes so much sense!
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.
Great video! Very clear explanations and the visuals were so helpful.
I find the explanations and animations extremely clear. Thanks for making this 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.
You are an absolute genius. You are a mathematician , a scientist , an artist and a teacher
Beautiful video. Never really thought that directed graphs could be this useful in DP!
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.
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.
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 ❤
Thank you for the video. Really pointed me in the right direction as to how to approach DP.
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.
One of the best computer science explanations on the TH-cam!!
Great video! Really liked the smooth animations!
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
Well done, what a great video. Thank you so much for taking the effort to make this, great production.
TH-cam recommended your channel to me yesterday. I wish I'd found you earlier! Great explanation and illustration!
This is so interesting to work through on my own, thanks for the video!
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!
it feels so good to like this video. Thank you so much for all the insight.
With your explanation, I actually find the topic interesting now as well!
Great vid!
Amazing and intuitive explanation. Great work!
The code tracing for the box stacking problem was amazing!
The DAG tip is super helpful!
This is a great video!! I have recommended to my friends.. nice work!!
The DAG bit is fascinating! Thank you!
Your question were so interesting. I loved those problems seriously. Thanks for this video very very much.
Best of explanation, visualization, succinctness with clearity and out of the crowd examples for this topic ever seen in a single video ! You got a subscriber ! BTW, which tool you use for the graphical visualization ? Do make a video on it as well ! Thanks a ton !!!
You deserve wayy more subscribers. Love the content, please keep it up.
You sir, are a wonderful person and I want you to know that you have changed someone's life today.
Loved the video!!!
It really helped me in understanding the subject.
All your content is very nice and so helpful and the way you add the background music is a good idea 😉👍
The explanation on the thinking process is really good !
thanks for this video!! i've really been struggling with DP while doing interview prep
This is a great explanation. Thank you!
Thank you very much.I love this method to explain.
Bless your heart lol was looking for someone to explain some intuition behind these magical solutions.
great video you made this topic fascinating. I really enjoyed watching through it!
Amazing explanation and narration style .. keep up the great work 👍
I was waiting for this amazing video. thank you very much.....
Wow! Finally a decent, informative, well-structured, and helpful recommendation from TH-cam. Maybe the algorithm is actually improving, or maybe it's just getting lucky once every five years. Regardless, you've got yourself a new subscriber.
Edit: wow, this was also the 5,000th video that I've liked on TH-cam. I expect you'll also be getting like numbers 5,001 through ~5,020 before the end of the day.
Great video. Visualization as Graph is super helpful!
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.
An absolutely wonderful video. Thanks!
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
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 !
This is definitely the best explanation I've ever seen about a classic DP problem. The animations and visualations give you the extra edge for sure! Would you consider making a follow-up to this video on how to solve the LIS problem in O(nlogn) time? Personally, I find that understanding the more efficient solution is much more difficult than the O(n^2) solution in this video.
For O(n log n) speed you can use segment tree to find maximum value of L[i] for fitting i, though that may require compressing numbers. Let st[x] be maximum length of LIS, that ends on number x(not index) that we have already encountered. Default values are all zeroes, except st[A[0]] = 1. Then we iterate through A[i] and use segment tree to find maximum of all st[x] among x < A[i]. Then we set st[A[i]] = that_maximum + 1 and move on. To get final answer just get maximum of all st[x](it will be in the root of segment tree)
Great tutorial. Thank you!
Wow! The best explanation ever! Love it! Thank You
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.
Thank you, this video really explained what Dynamic Time Warping is actually doing
Your videos are much helpful for learning the contents. Please upload more such contents. I recommended it to my friends.
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?
Yeah this is a masterclass in how to teach CS. Great job!
dude you are awesome! thanks for sharing these technique it helps me a lots!
Good video, I learned a lot, thank you for that. There are some explanations that felt a bit unclear, but maybe it's just me. I'll revisit the video later if I need to understand better.
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.
Bro, he complicated stuff even more. How is everyone in the comments complimenting him?
Fantastic explanation, thank you so much!
Thank you for this video. This really helped me unterstanding dynamic programming for an exam which will be in 2 days
thank you... you are one of the best teachers in the world
using the animations in the right way! great explanation
Thankyou
Awesome Explanation!! Thank you :)
Really nice channel and explanation. Subscribed and liked!
Very well explained video!
YOU ARE A LIFE SAVIOUR!! THANK YOU
The visuals were dope man
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!
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?
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 👍
thank you so so much, this video is absolutely a lifesaver!!!