5 Simple Steps for Solving Dynamic Programming Problems
HTML-код
- Опубликовано: 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
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
This is probably the best video about Dynamic Programming I've seen on RUclips, 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.
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 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!
Wow, you’re gonna blow up dude. These animations are insanely good for learning. Amazing work
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
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!
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*
Love this video! Really easy to understand and content is professional. Looking forward to more videos from you.
Thank you! ;)
Ага даже я все понимаю)))
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 am definitely sharing this video with my friends and so should everyone else!! Thanks for the amazing tutorial.
The Best part is you made us think through the process and how to break down a problem. Amazing work.
This video is so insightful! Thanks a ton for all the effort!
Looking forward to more :)
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!
Let's give this guy a real appreciation for visualisation, animation and clear cut explanation. Probably the best on this topic on RUclips ❤️
Such a great video again. You deserve much more recognition.
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
This video provides such great clarity about the steps and logic behind formulating a solution. Keep up the good work!
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.
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.
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 !
Best channel I have ever seen as a dev. So amazing and soothing at explaining concepts.
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.
Thank you for the video. Really pointed me in the right direction as to how to approach DP.
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
I find the explanations and animations extremely clear. Thanks for making this video!
Great video! Very clear explanations and the visuals were so helpful.
RUclips recommended your channel to me yesterday. I wish I'd found you earlier! Great explanation and illustration!
I have never thought to visualize DP as a DAG but it makes so much sense!
This is so interesting to work through on my own, thanks for the video!
I really like the way you both explain and visualize DP. Especially the visualization part.
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
Great video! Really liked the smooth animations!
Beautiful video. Never really thought that directed graphs could be this useful in DP!
Well done, what a great video. Thank you so much for taking the effort to make this, great production.
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.
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.
it feels so good to like this video. Thank you so much for all the insight.
The DAG bit is fascinating! Thank you!
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.
With your explanation, I actually find the topic interesting now as well!
Great vid!
One of the best computer science explanations on the RUclips!!
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!
I don't usually comment on videos but man this is the best explanation for a programming concept that I've ever seen on RUclips
Visualizing it as a DAG is such a nice new trick up my hat, thanks for this.
All your content is very nice and so helpful and the way you add the background music is a good idea 😉👍
Your question were so interesting. I loved those problems seriously. Thanks for this video very very much.
Bless your heart lol was looking for someone to explain some intuition behind these magical solutions.
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.
This is a great video!! I have recommended to my friends.. nice work!!
The DAG tip is super helpful!
Loved the video!!!
It really helped me in understanding the subject.
The explanation on the thinking process is really good !
thanks for this video!! i've really been struggling with DP while doing interview prep
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 are an absolute genius. You are a mathematician , a scientist , an artist and a teacher
The code tracing for the box stacking problem was amazing!
You deserve wayy more subscribers. Love the content, please keep it up.
Amazing and intuitive explanation. Great work!
Wow! Finally a decent, informative, well-structured, and helpful recommendation from RUclips. 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 RUclips. 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!
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 !
You sir, are a wonderful person and I want you to know that you have changed someone's life today.
great video you made this topic fascinating. I really enjoyed watching through it!
This is a great explanation. Thank you!
Bro, he complicated stuff even more. How is everyone in the comments complimenting him?
An absolutely wonderful video. Thanks!
I was waiting for this amazing video. thank you very much.....
the best video i have seen, thank you so much. I hope you always release excellent video
Amazing explanation and narration style .. keep up the great work 👍
Great Video especially the second example.
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)
Awesome Explanation!! Thank you :)
Your videos are much helpful for learning the contents. Please upload more such contents. I recommended it to my friends.
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 !!!
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?
Great tutorial. Thank you!
Thank you very much.I love this method to explain.
Fantastic explanation, thank you so much!
Aahhh, perfect video for quarantine.
You have great videos, love watching you
thank you so so much, this video is absolutely a lifesaver!!!
Great video! Watching with my whole college dorm. 🐍💪✨
Thank you. This video was very helpful.
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.
Wow! The best explanation ever! Love it! Thank You
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
The visuals were dope man
Thank you, this video really explained what Dynamic Time Warping is actually doing
YOU ARE A LIFE SAVIOUR!! THANK YOU
This is very specific to the problem shown. This cannot be generalized as the common steps for all dynamic programimng problems
Great video sir! I appreciate the help :)
Keep up the good work, man
Waiting for your videos
Very well explained video!
dude you are awesome! thanks for sharing these technique it helps me a lots!