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.

@su5k

2 жыл бұрын

hey there, it appears that the /lessons endpoint does not exist, although lessons button on the website redirects there

@ColinGalen

2 жыл бұрын

@@su5k whoops, should be fixed now

@godspeed2816

2 жыл бұрын

You must have told about the 3k likes in the video itself as most people won't see comments.

@knowledgedose1956

2 жыл бұрын

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

@ColinGalen

2 жыл бұрын

@@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'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.

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!

@alvesandre

Жыл бұрын

i do the same lol

Great contribution to the communilty. Thanks a ton for this amazing video

Thank you so much for this, I've been struggling to understand this for a while, now it's started to make sense

Was on this channel years ago, still underrated today!

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?

I am a fan and i like your videos ...plz keep going and share more topics like that ...

Thank You Colin for everything ☺

Thanks a lot for the amazing video, Colin! You're the best. :D

This is a fantastic start!

The Video is so good! Great Respect to you. 🤝

It is extremely helpful, thank you!!

Is it a full series on dynamic programming?

@ColinGalen

2 жыл бұрын

Eventually, I'll probably start off doing different things though.

I really fall in love with your confidence good job bro 🤎🤎

Thanks for the vid Colin!

Love you brother!! 🙌🙌🙌🙌

Much thanks, Great Great Job ♥️♥️

waiting for next videos 🤩😍

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??

Great work ! 😀

Hope there is dynamic programming on trees in details

It would be great if you could add stuff on advanced DP as well. This one was quite a good refresher for me.

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.

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).

@ColinGalen

2 жыл бұрын

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

@yi-minseah5330

2 жыл бұрын

@@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.

@kxb6098

2 жыл бұрын

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

@yi-minseah5330

2 жыл бұрын

@@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.

@kxb6098

2 жыл бұрын

@@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)

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

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?

THis was awesome!!

Hey!! Thats awesome 🤩🤩

Nice work you are my ideal

30 to 45 min is the best video length... 👍

Great video

Great video thanks a lot

Does this and the topic streams you covered before have the same material ? Should I start with the topic stream first ?

@ColinGalen

2 жыл бұрын

This is an introduction that explains the material, and the topic stream goes over a problemset that you can use to practice the material.

Hi, i love your video, do you mind if i tranlate this into Chinese and add it to captions?

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?

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 the vid :)

very nice video!

What i need to know before dynamic programming

@cross4326

2 жыл бұрын

Recursion. Understand it properly, otherwise you won't really get dp.

@Karansingh-vf7ei

2 жыл бұрын

@Just_another_soul thanks brother

@Karansingh-vf7ei

2 жыл бұрын

@@cross4326 thanks man

Thankyou Colin

Can you make a video on recursion it will huge help

Thanks!

wtf is this ?!! You are awesome man !!!!

Hey Colin! The link in the description looks broken, getting 404. Is the content shifted to some another website? Thanks for all your efforts!

thanks for considering the comments 28:45 this version is way better

I dont think that extra problem 2 is knapsack problem, you states the subset-sum problem.

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.

Why can’t solve extra problem 3 with a set dp? Just keep track of the path histories and compare sets.

Thank you

Thanks man

Thanks 🙏

YES!

Toooo goood

please do rec and bcktrck

Link in description is not working

Only Pro teachers know Why sharing slides is important

Hi, can I have the link to your discord channel?

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.

❤️

Hey Colin

Galen Colin op

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.

@ColinGalen

2 жыл бұрын

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.

@harshvardhanpandey8057

2 жыл бұрын

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.

@richtigmann1

5 ай бұрын

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

5:35

please do 1800+ there is already lot of beginner content

@gitlit5489

2 жыл бұрын

agree

@solaris413

2 жыл бұрын

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

@sarimahmed4219

2 жыл бұрын

@@solaris413 yeaahhhhh

@ColinGalen

2 жыл бұрын

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.

@TheCarloslucerna

2 жыл бұрын

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 ... 💜💚💛

@discrete42

2 жыл бұрын

No parts. Most people like binging.

thank you soooooooooooooooooooooooooooooooo muchhhhhhhhhhhhhhhhhhhhhhhhhhh @Colin Galen