Mastering Dynamic Programming - How to solve any interview problem (Part 1)

Wow, “recursion + memorization” is the most eloquent way I’ve ever heard it defined. Total crystallizing moment for me, even though I’ve used dynamic programming solutions before.

Tech with Nikola = Tequila 🍸🎉

All the great performers I have worked with are fuelled by a personal dream.

I think I understand it after rewatching at least 20 times. Putting that knowledge into code is a whole other story. I'm going to search for some more dynamic programming problems

This has to be one of the best dynamic programming videos out there. Props! Something that I feel could have been mentioned though is that a lot of the times it is also useful to reframe the problem which can make the solution a lot more intuitive as well. Whilst I understand that the point of the last maze problem is to teach DP effectively (it is a good and intuitive example for how a bigger problem can be reframed in terms of sub problems!), a useful observation is that the distance which the rabbit needs to move in an N×M grid is always going to be N-1 rights and M-1 downs. The number of ways is just the total possible arrangements of that many rights and downs, which is given by (N+M-2)! / [(N-1)!(M-1)!]. DP is thus not required for the last problem at all!

Very looking forward to the 2nd part!

Whenever a technical concept is being explained by an eastern european accent, you know you just struck gold.

thank you for creating videos like this. I've been in the industry for a couple of decades now and still learning new things and approaches. more power to you sir. and looking forward to more videos.

This video is epic. The way everything is explained makes it very easy to understand. The audio is super well recorded. The visuals are well done. If that's not enough, he explains the solution in code in both a recursive and not recursive fashion. I don't use recursion much, and I didn't really understand how to switch between recursive and non-recursive, and now I understand that better as a bonus. Instant subscribe. I hope you make lots of videos.

Really cool. Found this channel through the git video and started watching all the other videos. Really enjoying them so far, so thanks for making them <3

I don't know how, but your video came across as timely as ever! I am a student and I was given a recursion problem. It may not have been necessary, but I'm sure glad that I was able to optimize recursion (which is so much slower than the iterative approach that already for the 50th element you have to wait more than 30 seconds, when the iterative approach manages in less than a second)

Appreciate your video! I'm decent at algorithmic problems, and knew all of the basic dynamic problems you mentioned in this video, but I liked your emphasis on first writing a brute force solution and then optimizing it. I was a bit confused by your choice to always use bottom-up approach, because in my opinion bottom-up can sometimes be difficult to write as it can be hard to determine which states to update first. I've always found the recursive approach more intuitive, but maybe it's just me. Looking forward to part 2! Hope you can help me find some intuition to solve harder DP problems as those are still pretty difficult for me.

Fun fact, for the maze problem, you can also solve this with combinatorics. The key to note is that no matter the path, the number of right moves and down moves end up being the exact same. For the 18 x 6 grid example, you'd need to move 17 down, 5 right in total. Therefore, for 22 total moves, we pick 17 spaces for the down moves and leave the remaining for the right moves. C(22, 17) = 26334 This is equivalent to picking 5 spaces for the right moves and leaving the remaining for the down moves. C(22, 5) = 26334

Dynamic programming -> Dont do what is already done

Hope this channel grows a lot. I'm on mu first steps on coding, but I know it's gold.

Be thankful when you don't know something for it gives you the opportunity to learn.

Great video Nikola. I would love to see more of these in future. Once again, Thank you for this 😊

Hey, Nikola! This was a really useful video, as we're currently going through DP on my Master's. It's such a difficult paradigm to get used to, but your video really helped understanding the paradigm, and hopefully it'll help my future self learning the DP paradigm :) Also, any idea when the next part is coming out? :D

This was extremely useful and is one of the better dynamic programming explanations I've seen.

I remember solving the knapsack problem in C++ back when I was studying algorithms at the University. I found it so hard at first, but once it clicks it’s awesome