Understanding Dynamic Programming

This is an introduction to Dynamic Programming. It is an extensively used concept when solving problems for competitive programming and interviews.
Dynamic Programming involves taking a recursive approach to problem solving and then memoizing subproblem solutions. This works for a class of problems having the following properties:
1) Recursive
2) Optimal Substructure
3) Overlapping Subproblems
4) Memoizable
5) State Space is a Directed Acyclic Graph
These problems are solved by using either a top-down or a bottom-up approach. The Top Down approach uses memoization to avoid recomputing the overlapping subproblems. The bottom up approach is usually faster as it uses precomputed solutions to build a larger solution.
You will often find Dynamic Programming in interview and competitive programming questions. They usually rely more on intuition and mathematical clarity than deep knowledge of data structures.
References:
Introduction to Algorithms - Cormen
www.geeksforgeeks.org/dynamic-...
www.geeksforgeeks.org/dynamic-...
#dynamic-programming #competitive-programming #coding-contest

[@gkcs]

Hi guys! I would like to clarify for the point made at 3:56. Optimal Substructure means that the given problem can be solved by solving it's subproblems optimally. We can then combine those optimal solutions to get the current problem's optimal solution. Cheers!

[@ttwdp]

Gaurav Sen My favorite series has aired now after BBC's Sherlock. 😃

[@aaryanpakhrani5671]

@@ttwdp 😂

[@abhishekkumar-os5zk]

i was about to comment that mistake you cleared that up here .

[@Mohit-cn2us]

Dynamic Programming = Remembering the past ;)

[@farhan787]

Dynamic Programming == Remembering the past

[@sagnikdas975]

Being a CS under-grad(4th year) I can definitely say that the work you are doing is bigger than most things.

[@gkcs]

Thanks Sagnik!

[@qwarlockz8017]

Hey Guarav, This is a really nice explanation. It is def important to hear different voices in different ways explain this complex ideas. Thanks for being a very clear voice on this subject!

[@gkcs]

Thanks qwarlock!

[@portlandsound1]

Guarav, thank you so much for putting this video together. This is the best explanation I have come across. I really appreciate it!

[@fahadahmad9881]

This is the best video on DP.

[@sourabhpukale4622]

Man let me tell you your future. You are going to get huge. Great job mate.

[@gkcs]

Thanks for the kind words Sourabh :-)

[@tanzzzzz225]

you were right

[@ekeemekalu7124]

You were right

[@sunnysrivastava7575]

It is like your best friend is teaching you dynamic programming ....loved it thanx and god bless you bro

[@gkcs]

Thanks Sunny!

[@shameer2876]

I am about your age dude and gotta say that you are amazing. Keep doing what you are doing.

[@kaushilkundalia2197]

This is the best video I've found on DP

[@gkcs]

Thanks 😊

[@rahulagarwal8059]

This is a very nice explanation on the concept of dynamic programming 👍

[@dpfit]

Hi Gaurav. I have been following your videos from a couple of months. I must say I am in love with your channel. All videos are commendable. Thanks a lot. Subscribed and turned on the notifications long back :D

[@gkcs]

Thanks Mr. Fitness!

[@akarshrastogi3682]

That's a good introduction to DP, unlike the cliched ones found everywhere. You're doing great, try to keep your teaching standards higher than standard texts like Cormen(MIT) so that it is truly fruitful to choose to watch your videos over reading a great book. Thanks.

[@gkcs]

Wow, thanks Akarsh! Thats a high standard to strive for, will try to do so :-)

[@rayhanmahmudshihab]

Excellent. And thank you very much for skipping "The great Fibonacci example" as that's damn boring... :p

[@gkcs]

Haha. I actually made a video on that after this :-P You could skip it though! Bitmasks is also out.

[@rayhanmahmudshihab]

:xD Actually, having a video on Fibo is good, but having new is always better ;) Thanks for both :D

[@TheDuhbin]

Thank you so much man!! You are awesome.

[@thecodespace]

till now i just knew that there is something dynamic programming . now after watching your video i can say that i am aware of concept of dp.

[@NohandleReqd]

Gaurav man, you explain things very clearly. That is a very important thing in DP. Could you take some complex problems (DP starters or some from atcoder dp contest) and go about explaining the base states, recursive equations, and the solutions? We all know the solution is pretty easy, but the thought process as to WHY my dp[0][0] would be 1 or 0 is important to understand and noones seems to explain it good enough anywhere!

[@KoustavG1]

Ei topic tar jonno wait Kore chilam. Thanks

[@gkcs]

Thanks Koustav!

[@sanketchobe9328]

Awesome! It was a very good and helpful video, can you please also explain the memoization or tabulation techniques used for dynamic programming. These are some tricky methods to understand while solving a particular problem with dynamic programming.

[@gkcs]

Thanks! You could try the dynamic programming playlist on the channel.

[@harshk2301]

GKCS is Awesome.!! :D

[@gkcs]

Thanks Harsh!

[@sidhantmishra2734]

liked it very much...please move forward without missing out any topic in dp thank you

[@gkcs]

Hi Sidhant, thanks for the feedback! :-)

[@madhubhargava5049]

You are doing a great job bro. Thank You!

[@gkcs]

Thanks Madhu!

[@suyashshrivastava596]

great work gaurav. It's really helpful :)

[@gkcs]

Thanks Suyash!

[@dreamtoreality445]

You are my friend. Good luck nice approach

[@muskanagarwal7937]

Please make similar series on Greedy algorithm containing different important problems from various cp sites with the approach to solve them.

[@gkcs]

Have a look at code_report. He has a great list 🙂

[@akshatsunny]

Paji, charan paji🙌

[@TheGamerGuy201]

Can you make a video about how to actually come up with a solution for a dynamic programming question?Like how to identify the states and form the recurrence relation?

[@gkcs]

There are quite a few videos in the dynamic programming series. You can have a look at them to develop an under for how dp states are recognized and solved.

[@Shivam22.1.97]

nice.....can you make videos on standards we need to follow during cp

[@johnz1611]

Hello Gaurav, Firstly, great effort and thanks for making the videos on DP :) I have a request, I think it would be awesome if you made some videos on throwing some light on the recurrence relations for these problems .. It would be very helpful, if you made a video on how to come up with these recurrence relations, the intuition behind coming up with them and the bases cases .. Recurrence relations are not always straight forward and obvious and so are the bases cases. So, it would be great if you could consider it and help us out :) Thanks

[@gkcs]

Hey John, thats some great feedback. Will definitely take it into account when explaining DP, and hopefully I can make a video specifically for this. :-)

[@johnz1611]

Gaurav Sen that would be great. Because if u look around there are not really many videos or other resources which explain recurrence relations in a good way. I feel that you have an opportunity to fill that missing link and since you are great at explaining things, I am sure it would be of great help to many people out there. Looking forward to that video :) thanks

[@manan4436]

Thanks for video. Please also upload about graph theory in competition coding. And also how to find .. given problem can be solved by dp

[@gkcs]

These will come out soon :-)

[@prafful1723]

awesome work

[@gkcs]

Thabks Prafful!

[@rajdeepchandra9807]

Quite informative.

[@gkcs]

Thanks Rajdeep!

[@praveenak]

Isn't bottom up approach inefficient in this case? For given N you need to compute all the values up to N-3. We will be doing lot of unnecessary computation. I can see that, bottom up approach works for this example, but if slightly change the problem and remove f(n-4), we don't have to compute f(7). Otherwise great video. Keep it up.

[@gkcs]

Thanks! Both approaches take the same time complexity. Bottom up finds all sub solutions. The top down stores them after finding them. If the bottom up is computing more states than required for the general algorithm, then we have the DP state space defined incorrectly.

[@sidhantmishra2734]

apart from this, also look towards ds, as to when the question of using ds like hash and dequeue comes. How we will recognize it?

[@tanzzzzz225]

I can identify the dp problem. But i really struggle when building the core logic. Like how we populate the matrix

[@supriyantapoddar6129]

we want this series to be more precise to get this topic from the root.Thanks... :)

[@gkcs]

Thanks Supriyanta!

[@mohammaddaud5162]

In Further Videos If you will explain TOP-DOWN method to BOTTOM-UP by method of directed acyclic graph or anything Will feel very haapy :-)

[@gkcs]

Hi Mohammad! Will try to do that in the complicated ones. Coming up soon! :-)

[@srinjoychoudhury2246]

Hey GKCS could you give some easy or basic dynamic programming problems.I just got started with it so was needing some idea. do keep making more on dp

[@gkcs]

Hey Srin, you could a have a look at the codeforces site for some good dp problems. Their contests have a progressive question difficulty. Thanks for the feedback :)

[@srinjoychoudhury2246]

thanks for your feedback. Do make some on data structures as well.

[@bckzilla]

I don't get it. If we are in state (1), why would we need states (2) and (3) to get to (6)? To me it seems there are one and only one way to get from state (1) to state (6), and that path relies on no other states?

[@tomasjason5286]

amazing ;-)

[@venkateswarank1145]

Hi Everyone, Can someone say the difference between Optimal Substructure and Divide and Conquer ? Both seems to have a same sound to me. TIA

[@gtracer9182]

In divide and conquer, the substructures do not overlap i.e, you cannot reuse calculations made to solve one subproblem in another. But they overlap in the case of dynamic programming.

[@johnenthu9643]

Sir i can't able to recognize the recursion part in dynamic programming then what to do sir??

[@gkcs]

Well, then you are in big trouble, aren't you? :-p Seriously though, don't be too harsh on yourself and make sure you understand concepts like finite automata and recursion first. Lakhs of people before you have done the same. Hard work is the only way forward for these cases :-)

[@johnenthu9643]

thank sir

[@pradipjadhav4545]

What is mean by recursive method

[@rohitshekharsingh2579]

what is GKCS ??

[@SomnathMukherjee1112]

Could you please tell me how to solve Little Rabit and the XOR Tree? www.codechef.com/problems/BTCD1510

[@unsaturated8482]

i was the 6.4k subscriber

[@gkcs]

Thanks, and congrats!

[@AtulkumarGupta080796]

please make a video on reducing states of dp

[@gkcs]

Have a look at the remaining series to see how DP problems are defined and solved. Especially Bitmask problems, where states are reduced to manageable numbers.

[@alanchua9631]

Hey, gkcs, really like your short videos. I subscribe to your channel after u say "we should contribute back". If possible, u should have videos on coding a problem as example .🙏🙏

[@asdfghjkl4735]

I agree, mainly in C++.

[@alanchua9631]

NISHANK BHATI yeah. C++ is one of the popular language. I seen most gkcs video, think he towards Java

[@gkcs]

Thanks Alan! I believe we should :-)

[@vaideshshankar9899]

its all a deception.....oh no😯

[@harshitachaurasia1246]

looks like cnn though😅