A Deep Understanding of Dynamic Programming [Intro / Overview]
HTML-код
- Опубликовано: 30 июн 2024
- Here's a post describing my current goals for the website (they are very cool, and will involve a system that auto-debugs your code): • Post
Link to this lesson on the course's website: [gone for now, sorry]
Currently, judging/debugging capabilities are not available yet, but it does have a text version of this lesson and some links to places to submit the problems.
Slides link: docs.google.com/presentation/...
Good tutorial on recursion (until I release one myself): • Recursion for DSA/CP :...
Timestamps:
Intro/resume 00:00
Structure 01:05
What is DP? 01:46
Setting up the problem 02:16
An iterative solution 03:13
A recursive solution 06:54
Vocab 09:37
Tricks for solving problems 13:23
Extra problem 1 16:23
Extra problem 2 19:05
Extra problem 3 22:33
Recursive vs. iterative 24:10
Extensions of DP 26:10
Conclusions 27:48 
Наука
Making videos like these - preparing the video, text version, practice problems, etc. - takes an immense amount of effort (~1.5 weeks went into this one alone, including a complete rewrite because it wasn't initially that good). Showing your support (e.g. by viewing/liking/subscribing) would help a lot with motivation and keep the good content coming. In particular, if this video gets 3k likes, I'll do another 7 practice problems (not the common/standard ones) with the same (or more) level of detail as in this video.
hey there, it appears that the /lessons endpoint does not exist, although lessons button on the website redirects there
@@su5k whoops, should be fixed now
You must have told about the 3k likes in the video itself as most people won't see comments.
Nice video, thanks for the content! done my part(sub/like/comment)
The guy above made a good point. You should have said about like in the video itself
@@godspeed2816 Honestly, that goal was set with the expectation that the video would do much better in the algorithm, so even mentioning it in the video probably wouldn't have been enough.
I'll probably just tone down my expectations for the future.
I just want to say, you are doing a great work. A big contribution to this society.
We all will support you in every step.
More power to you brother ❤️
I used to watch Netflix while i ate, now I watch your videos, I pause, think (yes, while I eat) on how I would approach, and then unpause to see how you solve it. Please keep on uploading great content like this, this is a great community that you are building, and we fully support you!
i do the same lol
best overview till now for dp , as a beginner after 2yrs also it is latest i think , thanks @Colin Galen , i have been watching many of your videos nowdays, and i think your demonstration skills are pure gold
I've been spending so long on LC and basically getting depressed as it takes me forever to complete the most basic problems. I figured I would instead spend that time deep diving into theory instead and only attempt problems after understanding that theory and your videos do not disappoint! It feels like before I was trying to fix something without the tool to do it! TYVM for being transparent and putting your time and effort to help people like me who are completely lost on this stuff.
Was on this channel years ago, still underrated today!
Thank you so much for this, I've been struggling to understand this for a while, now it's started to make sense
Great contribution to the communilty. Thanks a ton for this amazing video
This video is great. Exercises 2 and 3 felt challenging, and I think that's a good thing, since most educational sources tend to use trivial examples.
Great content as usual , Keep up the good work bro
One of the best videos on dp ever!
This was a really informative video! I already knew quite a bit about DP, but watching this video really connected the dots. The idea that 2d DP is equivalent to any grid problem was also incredibly insightful and helpful. The comparisons between push/pull and recursive/iterative was also super helpful too. Very good video!
P.S. where is convex hull trick and segment tree video?
This is a fantastic start!
Thank You Colin for everything ☺
I am a fan and i like your videos ...plz keep going and share more topics like that ...
Thanks a lot for the amazing video, Colin! You're the best. :D
It is extremely helpful, thank you!!
Love you brother!! 🙌🙌🙌🙌
The Video is so good!
Great Respect to you. 🤝
Thanks for the vid Colin!
Much thanks, Great Great Job ♥️♥️
Great work ! 😀
Is it a full series on dynamic programming?
Eventually, I'll probably start off doing different things though.
waiting for next videos 🤩😍
THis was awesome!!
Great video thanks a lot
Nice work you are my ideal
I really fall in love with your confidence good job bro 🤎🤎
Thanks for putting this together. With the thought and effort that went into this I'm sure many will find it helpful!
For extra problem 3 (24:41), I was thinking that you could formulate a recursive dp(visited mask, last visited cell), although that'll be less efficient than brute force since you'll try to recurse through a lot of impossible states. Or... you can do an iterative push dp[mask][last cell] with a queue so that you always process masks with fewer set bits. But I think that the reduction in case vs. brute force wouldn't be much since you only save on the cases where a corner in the profile is the last visited cell (i.e. "corner cases" haha).
Yeah, it's hard to tell how comparatively fast a bitmask dp formulation could be, though either way it would grow so fast that it's impractical in terms of time limit no matter what. The brute-force would be, in the absolute worst case, 3^(n^2) since you have
@@ColinGalen Yep. About the timestamp, the ones you provided are correct. I think they didn't work for me earlier because I tuned in a couple minutes before the stream started.
shouldn't it be clear that no kind of dp is applicable here because the path itself is a state, so every state is visited just once, hence no repeated work and no dp
@@kxb6098 My thought is that instead of the path, the state could be the visited cells (which cannot be revisited) and the last visited cell (the "head" of the path). These 2 factors are sufficient to describe what moves can be made in the future. And if you define the state like this, there are multiple paths than can make the same equivalent state. Thus you have some reduction in cases to examine. You may want to imagine a 3x3x3 block starting at (1, 1) and ending at (3, 3). Right away I can imagine 2 different paths to reach this state (zig-zag starting by going right, or by going down). If you simply mark dp(mask for 3x3, 3, 3) = 2, then you can just propagate from this 1 state, instead of from the 2 aforementioned paths.
It wasn't a great idea for me to this up though, as this discussion may be inappropriate for an introductory video to the dp topic.
@@yi-minseah5330 you're right, if you define state like that then there are multiple paths leading to same state so there is repeated work, and time complexity would be (n^2)*2^(n^2)
Hope there is dynamic programming on trees in details
Great video
Hey!! Thats awesome 🤩🤩
Thankyou Colin
Thanks for the vid :)
Thanks!
It would be great if you could add stuff on advanced DP as well. This one was quite a good refresher for me.
very nice video!
13:23 you don't have to rely on intuition, all dp problems have similar properties.
1. Does it have repeated recursive calls if solved recursively?
2. Does it have an optimal substructure i.e. the optimal solution of a subproblem used to find the optimal solution of the original problem?
If a problem has both of these, dp is a good tool to solve it. If it only has one, then another approach would be better (greedy, divide & conquer, etc.).
I don't think the knapsack problem is very well explained here since the problem is more to do with the optimization of getting some maximum value(that's limited by T), not the exact T value as you showed. I found the video quite interesting regardless. Thanks for putting it together.
Thank you
What i need to know before dynamic programming
Recursion. Understand it properly, otherwise you won't really get dp.
@Just_another_soul thanks brother
@@cross4326 thanks man
I have a question about Extra example “2”
Does the solution take into account that we cannot take the element more than once
,or I can already take the number any number of times??
I believe every word colin says. Very nice video.
Just wanted to ask, when we're writing iterative code, we can do anything, push or pull dp whichever's easier for us right?
Thanks man
for extra variation (shortest path), I can solve with brute force but not sure how to apply memoization as I think we need to back track to previous sub nodes to update their minimum cost to the target/ goal cell
Thanks 🙏
Hi, i love your video, do you mind if i tranlate this into Chinese and add it to captions?
YES!
30 to 45 min is the best video length... 👍
Does this and the topic streams you covered before have the same material ? Should I start with the topic stream first ?
This is an introduction that explains the material, and the topic stream goes over a problemset that you can use to practice the material.
wtf is this ?!! You are awesome man !!!!
at 20:39 if we too the number at pos 1 [if 1 based indexing is considered] then, if we take the target must have been 7, and in case where we don't take that number then it should be 10. Am i right or wrong?
thanks for considering the comments 28:45 this version is way better
Can you make a video on recursion it will huge help
Toooo goood
Hey Colin!
The link in the description looks broken, getting 404. Is the content shifted to some another website?
Thanks for all your efforts!
grid path with four direction possible with restriction of every cell should be visited once. Its not solvable by dynamic programming cause its lacking optimal substructure property right?
I dont think that extra problem 2 is knapsack problem, you states the subset-sum problem.
Only Pro teachers know Why sharing slides is important
Why can’t solve extra problem 3 with a set dp? Just keep track of the path histories and compare sets.
please do rec and bcktrck
❤️
The concept is very simple: for certain computations, you need to compute a number A that depends on some other computations, which may take a lot of time. Then later on, you reuse this result A a lot of times, maybe as a part of bigger computations. So, instead of re-computing A every time, you store it somewhere.
As simple as that. It is even obvious as a sensible thing anyone would do. The word “dynamic programming” makes in sound complicated.
Link in description is not working
I fail to comprehend, why extra problem 2 is a 2d problem.
We have a set of give numbers A. We are seraching subset of A, sum of which = T. Where does the 2nd dimesion come from? What does it represent?
The code isn't intuitive enough for me, since it's just iindexing over 2d array by i and j.
Also, can't see declaration of arr variable for both iterative and recursive methods. This is super confusing.
Hi, can I have the link to your discord channel?
Hey Colin
5:35
I think most of us are fed up with seeing the same fibonnaci/lcs/coin change/A and B of atcoder dp contest, whenever someone makes a video on dp. There are hundreds of videos that literally cover these 4 - 5 standard problems and call it a day. Please cover something different like solving difficult dp problems from cf or other ojs.
There is some merit to having problems be repeated - you're already familiar with them, so you're more open to different perspectives and ways to think about approaching them. I would not consider my perspective on DP "average", so there is a lot of good stuff to get from this video.
That being said, I get it. This is only the first video - while I probably won't do that specific thing, there will be a lot more DP to come.
I have seen comments like these multiple times and I think there is an point that needs to be addressed ( please don't think that I am accusing you in any specific way, most of this is just based on what I thought when I was beginning with dp)
At the beginning, DP is one of the first topics one encounters that you cannot easily draw a real life parallel to (for example binary search is compared to looking for a word in dictionary, graphs are compared to family relations etc). This leads to some trouble in understanding the concept. When one looks at a tutorial on the topic, you get bombarded with classic problems and the focus shifts from understanding the underlying logic to learning the solutions of specific problems. These problems are however just examples like that you would find in a math book. The real point is to understand the solution to the point it starts becoming intuitive. Ask questions like why is this variable used to define a state and not some other?
And if you can understand the steps to approach these classic problems then you can solve upto 1700 ish rating on cf (being conservative here tbh).
Also, the most important ingredient that maybe you can skip is giving things time. Since dp is different to things you've encountered, it may take some time but don't worry you'll get it.
I actually think that this is a very good take on them, because we're shown both iterative and recursive solution, as well as them being fully explained, so i see it as quite good actually
Galen Colin op
please do 1800+ there is already lot of beginner content
agree
i m fed up of same fibonacci/coin change and atcoder dp contest problem A and B take it as a request recently one channel take u forward also uploaded dp from beginning its too good for beginner level now please make something different it will help the community more
@@solaris413 yeaahhhhh
Beginner content is good for starting momentum. But this course opens itself up to a wide variety of content - there are some parts that can be tailored to beginners and some that can be tailored to the more advanced crowd. So later on, there will be more advanced content and more difficult problems.
No
Don't upload too long videos... Instead make parts of it and happy to see dat its beginner friendly..Moreover help us with intuition ... 💜💚💛
No parts. Most people like binging.
thank you soooooooooooooooooooooooooooooooo muchhhhhhhhhhhhhhhhhhhhhhhhhhh @Colin Galen