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

🎬 Mastering Dynamic Programming: An Introduction 🎬

Are you ready to unravel the secrets of dynamic programming? 🤔 Dive into the world of efficient problem-solving with this comprehensive introduction to dynamic programming. Whether you're a budding programmer or an algorithm aficionado, this video is your gateway to understanding the magic behind DP.

🔑 Key Takeaways:

📌 Demystifying the concept of dynamic programming.
📌 Understanding the core principles behind dynamic programming.
📌 Unleashing the power of recursion and memoization.
📌 Step-by-step breakdown of dynamic programming problem-solving.

Dynamic programming is like a puzzle-solving technique, and this video is your ultimate guide to fitting the pieces together. Get ready to elevate your coding skills and witness the art of optimization in action.

🚀 If you found this video helpful, don't forget to like, share, and subscribe for more tech tutorials!

🔗 Connect with me:

Timecodes
00:00 - Intro to DP
01:40 - Problem: Fibonacci
04:44 - Memoization
06:22 - Bottom-Up Approach
07:20 - Dependency order of subproblems
07:52 - Problem: Minimum Coins
13:39 - Problem: Coins - How Many Ways
15:22 - Problem: Maze
18:55 - Key Takeaways

[JulenSanAlejoGonzalez]

Dynamic programming -> Dont do what is already done

[dave]

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.

[divy]

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!

[patrickstival]

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

[miguelrosa]

Dynamic programming is recursion + memoization, thank you so much I will never forget that connection, it made de concept click for me.

[pubringjuandelacruz]

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.

[rodneymkay]

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

[driden]

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

[franepoljak]

This is by far the best explanation I've ever seen for dynamic prorgamming!

[systemloc]

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.

[priyankthakkar]

Wow.... A great video to start with dynamic programming. It is like brain is forced to think after a long time

[zsjvdso]

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

[tahawahiddaw]

every second of the video is worth watching, please keep bringing up such videos and thank you so much for explaining the DP in such remarkable way

[SALOway]

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)

[temurson]

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.

[AusReddit]

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

[pet.me]

Not gonna lie, I have watched a few videos about dynamic programming, but your video is the only one that I love the most and understand because it has examples lol. Keep up the good work bro, I already subscribed.

[bdtrczp]

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

[tkingless]

I knew the examples but not knowing what dynamic programming is until watching this nice explanation. It is like connecting broken pieces into a large one. look forwards to next part

[dxkilcj]

this was quite a unique way to explain dynamic programming !