Hello all and welcome back.
So in this video let us continue our discussion on dynamic programming.
And now let's understand what exactly is dynamic programming through an example.
So if you all remember we understood about recursion using a Fibonacci number code.
Right.
So let me just write down the same thing Fibonacci.
Series.
Now the series was defined something like this.
Let's say the first number is one, then one.
Then each and every next number is going to be equal to sum of previous two numbers.
Right.
So it will be three, then five, eight, 13 and so on.
Now when we were doing this Fibonacci series, if all of you remember the code which we wrote was something
like this.
So let's say if it is.
Using recursion.
Something like this we used to do so if my n is less than or equal to say one, then I can just return
one.
Else I use two return.
FIB recursive.
N minus one plus fib recursive.
N minus two.
Right.
So this was the way we were doing this particular question.
We are using the Fibonacci using the recursion concept.
We were able to solve this question very easily, but when we learned about the time and space complexity
there, we saw that let's say if I'm calculating the fifth Fibonacci number.
So let me draw the tree as well here Then this is something which we followed, right?
So in it here, let's say if we start from five, then each and everywhere we will have to make two
calls.
Let me just draw down the tree once so that it is a lot clearer.
And as discussed in the last class, everyone last video that without recursion understanding deep is
not possible.
So a very humble request that please make sure that you are spending a good amount of time on understanding
what recursion actually is.
How it works.
We have done the same, and I am really hopeful that you have not skipped that particular section.
Section or the section, right?
So great everyone.
Now, I think this can be the tree that we write down for five.
Five is going to make call for four, 4 to 3, 3 to 2, and then finally a call to one is also going
to get made Here.
This two is also going to make a call for zero.
And in this way our tree used to get made.
But something which we didn't realize at that time when we were understanding this in recursion, is
that five is going to make the call for three here.
Three is going to again make the call for two.
This four is going to make the call for two as well.
So I am making a lot of multiple calls right.
So if we see in this particular example even we have two called multiple times.
So this is first second and third right.
In a similar way if I move forward a lots of number they are going to get get called multiple times
in this whole recursion tree.
Right.
So this is going to now call for one.
And this is going to call for zero.
In a similar manner if you see for one for one I am calling it a lot of time as well.
So it is first, second, third and fourth.
So the basic thing, which I want all of you to understand is that we are making a lots of.
Duplicate calls.
Right, everyone.
So we are making lots of duplicate calls.
And because of that, what is happening is that I am not able to remember the solution.
And I have to make this call again and again and again.
As our tree will grow more, you will see that each and every call is getting made multiple times.
For example, here one will be getting called 4 or 5 times, then two let's say three times three will
be two times.
Okay.
But as we grow our tree, let's say for n is equal to ten, we will see that these calls will also increase
with a great magnitude.
If all of you remember the time complexity which we calculated was somewhere around two to the power
n time complexity of our recursion code, right?
So it was around two to the power n.
Now, the major problem in this particular time complexity is that yes, it is very bad.
But if we just try to visualize or see the tree, you can be sure of one thing that we just want.
Okay, so let me write this down.
We are just making.
N plus one unique calls.
What do I mean by that is I am making for n is equals to zero okay.
So from zero all the way to n these are just the numbers which I'm calculating, but since I am not
storing their answer, I am calculating them again and again and thus making this complexity a lot.
Bad, right?
So I just need to calculate these n plus one numbers.
Right.
But for that I am trying to calculate them again and again not storing the solution anywhere.
And thus the problem is that we are making it a lot more complex in terms of our time complexity.
The same reason we saw that for n is equal to 50, it will never be giving us the answer.
Okay, so let us try to see this a little bit more in code and the visualization.
So let's go back to VS code.
Everyone here.
This is exactly the code which we talked about.
Just that I have taken the five one and five two as the variables.
Let us have one thing here as well.
So what we can have is a dictionary which is called.
And every time we come here, all I have to do is if.
N or let's say.
So here we can check if n in my d one or sorry calls.
If it is present then I have to say that okay this is the first call.
So calls of n equals one.
Else what we can do.
Calls of n plus equals one.
So all I'm doing here is I am calculating that how many calls I am making for a particular number.
Let us do one thing now Fibonacci number let's say of five.
And after that let me just print the calls dictionary and let us print the answer here as well.
So I will repeat exactly what we have done.
Everyone.
This whole code is just the code for calculating recursively a Fibonacci number.
I have just added a dictionary to understand that okay, for each number, how many calls am I making?
Okay, so let me run this.
Okay.
So it's giving an error.
It's saying that key error five is there.
Okay.
Let us check that.
Okay.
So seems like yes we have made a mistake here.
So it should.
If not in, then we should be adding it here.
Else we should be improving.
Just increasing that.
So let us run this again everyone see.
So yeah we are getting these calls.
Let us see them in a little bit.
Yeah.
Okay.
So it is giving me minus five.
That seems to be wrong.
Let us correct this.
We should return one.
Great.
And it should be this.
Now it will work fine.
Great.
So see this everyone.
Now what exactly is happening for five?
I am just making a one call for.
For one call for three.
Two calls for two.
We are making three calls for one.
This is five.
The problem happens if I make it ten.
And if I run this now if you will see how the calls are increasing.
Right.
See this now.
So effectively I will just repeat what we have done here.
We are calling our Fibonacci number recursively.
And I am just making sure that in this dictionary I am maintaining that okay, which is the number and
how many calls we have made so as to see that actually, are we doing any repetitive work or not?
Here it seems like yes, we are doing a lot of repetitive work, as we can see in front of us with these
calls.
So one is getting called out 55 times.
234 321.
Okay.
Just to make sure that we are able to understand the scale with which it increases, let me make it
15 and hope it gives us the answer.
And now if you will see yes, 15 is just 114 one.
But see four is getting called, 144 times five is getting called 89 times.
But if you understand, just one thing here is that I am just calculating numbers.
The calls are just being made for zero till 15.
Okay, so there are n plus one numbers which I have to calculate.
So for n equals 15 I should just start from zeroth Fibonacci number and go all the way till 15.
And that is where that is.
Sorry.
All the numbers which we have to calculate.
But because we are not saving the result I have to calculate them so many times and you can see how
the scale has increased, right?
Again, if I will do it 20, it will just blow out of proportion.
We will be making so many useless calls which we could have avoided just if we saved our results.
See 1597 times four is getting called.
Okay, let us try to understand this via our visualization as well.
So I found a very good overall resource for this.
Now let me run this for Fibonacci six let's say and let us run this and we will see in front of us the
whole tree getting made.
See the whole tree, the one way we made for recursion, right?
It is just assuming that the first number is zero.
We assume that to be one, but that should be fine, right?
So see for two how many times we have to solve it.
Two again.
So we are solving for two five times.
Similarly for three, 1233 times.
Okay, I hope you get the idea.
All this is happening because we were not storing the result.
If we would have somehow stored our result.
Let this code know that.
Hey, I have calculated for this number already.
Please don't do that.
Moving forward, we could have just avoided this thing.
And this is the reason.
If I maybe run it for 50, it's going to take maybe hours to complete, right?
If I run this now, it's going to take a lot of time.
Like for 50.
It can happen that we can actually calculate that manually quickly then waiting for this code to run.
So we see this now that this code overall has a limitation.
And that limitation is that because we are doing so much of repetitive work, we are not able to get
our answer in optimized manner.
If we take the assumption two to the power n calls we have to make, and we all know how big two to
the power of 50 can be, right?
Great.
So pretty sure.
Now the problem is clear, everyone.
And that is why I started deep with that quote that those who don't remember the past are condemned
to repeat it.
So because we are not remembering the past, that hey, if we have calculated this particular number
or not, we are a lot more overall condemned, that we are more likely to repeat that something which
we are doing.
Okay, so with that, I hope the basic idea behind deep is clear.
Now let us see what all we have understood by this.
So the major takeaway everyone is that we should somehow.
Store.
The results.
For.
numbers we already have.
Calculated.
Fibonacci for okay.
Fibonacci.
Our answer for.
So the whole idea is that if you are able to calculate anything once, we should not be repeating the
whole process, right?
That is the whole major idea.
Now let us move forward and see how can we do that.
I think the easiest way for doing this is that we can maintain a list.
We can maintain a list which stores?
The answer?
Already?
Calculated.
Okay, so till now we have already seen that how maintaining a list like what exactly list is and how
that all can be used.
Now what we all just be doing.
We will be maintaining a list.
Let us call that list diary okay.
So let us now try to make a Fibonacci optimize.
So diary one minute.
Yeah.
Great.
So minus one we have to just make sure that.
Yeah into.
N plus one.
So let me take n as five.
Great.
So what we are doing everyone exactly is that we are maintaining this diary where we will be storing
our answer.
Hopefully before this code runs we will be able to understand DP properly.
Okay, great.
Now let's see what's going to happen.
Fibonacci with DP Deep.
Okay.
That is the whole process behind dynamic programming.
Just that hey, let us store our answer before you give it back.
So the code is going to be the same majorly.
But this time when you are returning it, this is in a way you have calculated this answer, right?
So when you return it after that, we can do our work, but it will be a little different this time.
How it will be different.
See, now I am storing this minus one here because I want a differentiator that if this was particularly
calculated or not.
Okay, let me zoom it out only.
I am storing minus one here because I want to have a differentiator that hey, have I calculated this
before or not?
So see, let's say you asked me for Fibonacci of five.
I will just check if diary of N, which is your five.
If it is not equal to minus one.
That means I already have the answer, and you can use this directly so I can return this as it is.
If that is not the case, if that is not the case, and let us try to draw how a diary will look like.
So pay attention everyone.
The way our diary is going to look is something like this.
We will have zero, one, two, three, four and five.
Now when you want this five.
Okay, I am just storing minus one everywhere.
Now when you come to five, I first check if it is minus one or not.
If it is not minus one then I can return you the answer because I am sure that this is going to be the
answer.
So that is why I have used minus one.
Here you can use zero as well.
One you cannot use.
The reason is that one is answer for zeroth And first Fibonacci number.
Okay, again, you have to choose a number which you are sure is not going to come ever in your answer.
Similarly, you cannot use ten or any other overall identifier for that.
Right.
So minus one is a very good identifier because we know that our Fibonacci number cannot be negative
as well.
Now pay attention everyone.
What exactly are we going to do this time?
Again I can just copy the code.
I can copy this code again.
Now all I'm doing is when I calculate them, when I have this Fibonacci one and Fibonacci two.
I think it's a very good habit that I should store them as well in my diary.
So let me just make it diary, okay?
Because we have calculated, right?
We have got the answer.
We should be storing them in our diary again.
So Fibonacci diary of n minus two, Fibonacci two.
Now my answer is going to be 51 plus 52.
I can return this answer.
Very well.
I can return this answer.
Okay, just one thing to focus here again, everyone, is that we should store this answer as well.
If you have calculated this answer right, it's always a good habit to store this answer as well.
Because tomorrow if someone comes to me again, hey, that you know five, I should be having that answer,
right?
If that number is required again.
Plus, when this will boil down to recursion, then we have to make sure that intermediate answer we
are storing as well.
Okay.
Let me just stop this everyone.
And now let's try to see few things.
What if I am calling Fibonacci with DP.
Let us call it for five first okay.
And I'm able to get my answer.
So this is it.
This calls we can remove as of now because we are not using that.
So one second.
One mistake.
Yes.
So we should just also do one thing.
We should call this function now, not the other one.
Great.
So we see that the answer we are able to get as eight.
Okay great.
Let us try to understand this a little bit in few multiple things.
First let us try to do this in Python tutor.
Okay.
Let me remove the different other functions.
And please make sure that you understand this very properly.
There is a reason I am making sure that I am helping you visualize each and every thing.
Okay, let us remove every drawing.
Yeah, great.
So pay attention everyone.
What exactly is going to happen?
This is our whole code.
Let me just edit this code and remove these extra spaces so that it is better overall to run.
Let us now visualize.
So pay attention.
We make a diary and everything is minus one here.
Then we go forward and define this function Fibonacci with DP.
Then I'm calling Fibonacci with dp for five.
If you remember in the last video I told that Fibonacci DP is just making sure that we are storing solving
a subproblem once and storing their solution.
And if you will see via this diary list, I have done the same thing.
Once I solve the particular subproblem, then I will be storing that right and if required, I will
just give you the answer from my diary only.
Let us move forward now everyone.
It's getting called for.
N is equal to five.
Is n less than equal to one?
No.
So let us move forward.
Is diary of n not equal to minus one?
No, that is also not the case.
So let us move forward again.
Now you will see Fibonacci of one getting called for n is equal to four.
Similarly, like this, I will be making these calls for three, then two, and finally for one.
When I make this call for one, I have reached my base case, so I will be returning this one.
Okay, so one gets return every one.
You will see it here as well.
When I return this one I have got Fibonacci one in a similar manner.
I am going to call for zero and I am going to get one here as well.
Okay, so I will return one here as well because this is the base case.
I have five one and five two and n is equals to two.
I can calculate my answer and see what all I am doing.
Everyone.
Diary of n minus one n is two here.
So diary of one becomes one because I have calculated this answer.
It makes a lot of sense for me to save it in my diary moving forward.
Diary of N minus two.
Again, zero is one.
And now I am calculating my answer.
Answer is two.
And before returning this answer, I am storing this in my diary of N which becomes two.
Diary of two is two.
Let us move forward right now.
This time, this three.
It made a call for Fibonacci of one and got the answer as two.
Next call it's going to make on Fibonacci of two.
So let us see that Fibonacci with dp n is equals to one.
This is going to be a base case.
We also have this stored in our diary.
So it should be straightforward.
And we can return directly.
Okay so we got both the things and we can move forward.
And if you will realize we have done lots of steps for this n equals to three right.
We made a call to two.
Then we made a call to one then saved all these answers.
Now I have got my answer.
Answer Fibonacci of one plus two is three.
What I have to do I am storing this again.
Diary of three and I can move forward.
Okay, great.
Now this Fibonacci with DP.
It got an answer for three.
Okay.
It is going to make the next call for two okay.
But this time for two I don't have to make calls for one and zero.
If you understand this if you draw just the tree.
Right.
So pay attention everyone.
Five made a call on four.
Four will be making a call on three three making a call on two, then two for one and zero.
Every time I'm calculating an answer, I'm saving that as well, which you can see in this list.
Now when this three is going to make a call on one, I return because it's a base case.
The real benefit happens here when this for now is making this call to two, I will go and check in
my diary and directly return the answer.
I don't have to make these calls moving forward.
Okay, so again, just by adding two three lines, I have saved my answer.
And because I know that hey, I have calculated this before, I am not going to calculate it again.
That's the whole basic idea behind DP.
It is taught in a very difficult way.
I don't want you to ever be afraid of dynamic programming.
It is just this way of doing the question.
Majority cases.
In 90% cases, if you are well versed with recursion code, you can easily transform that code into
dynamic programming code.
That is something which I have done right in front of you.
Okay, and that's the basic idea behind solving DP questions.
The better you know recursion, the better you will be able to solve DP questions.
Now if you will see For N2.
I will not be making many calls and I have just written this, so I didn't even go to this level of
code.
Once I return this, I will be storing my answer.
I have 51 and 52 for N4.
Let me store this answer and you will see the answer here and go back.
So we are at the highest level for n equals five.
We got 51 which is 5452 okay.
It is going to make the call for three.
Again.
It would have made all these calls.
Haven't we saved our answer.
But being smart using DP we have made sure to save our answer.
And thus we can directly return the same, giving us Fibonacci one and Fibonacci two for n equals five.
Moving forward, we can just save everything.
Get the answer.
save our answer and finally return.
And you have the answer.
Okay everyone.
So we see eight here.
Now let us see.
The true power of DP and the true power of DP is that if it is 51 minute, let us make it 50 plus one
okay?
If it is 50 we get our answer.
And you can see how quick it is.
Whereas for normal recursive approach it will take ages to get your answer just because of the complexity
involved.
So again, I hope you are now able to understand that by just changing small things in our code.
By just remembering our answer, we are able to write a fabulous code which is able to run very quickly.
Okay, the basic idea remains the same that let us save our answer.
And now let me show you one more thing, which is the tree.
because I want all of you to understand and respect everything you understand and properly have the
intuition for everything.
Okay, so see, I'm just turning on this memoization.
So this whole process of adding the memory of adding the diary into your code, that is what is known
as memoization.
Moving forward, instead of diary, you will see me making a memo as a list.
Okay, so this way of solving is known as memoization.
The way I remember it, having a memory in your code.
Okay, in a way, this diary is a memory.
This is helping us not to forget the past.
And if we just run this now and this website, I will share with all of you.
See what's going to happen.
Call me to 654321.
Now you will see that we will not be making calls except for base case.
Multiple calls will not be made.
See to it.
Get for zero and one.
We save the answer, then three, two and one we got the answer for it, called for three.
Okay.
And for two.
But two is not calling downwards because we have this answer saved from here.
Right.
Let me just explain you pretty nicely.
So pay attention everyone.
So what is happening here?
See six made this call two five, five two, four, four, three, two and one.
Let us make a diary or memo list here zero, one, two, three, four, five and six.
Right now.
See what exactly is happening.
For one, we are calculating and we know the answer is one.
So we store that for zero.
It is zero, so we store that as well.
Now for two we are returning the answer as one.
And we store this three when it makes the call to one it's actually a base case.
Plus we have it saved in our diary as well, so we can return and say that hey, three answer is two.
As you see here.
Now when this four has to make a call for two okay.
For fib two that is n minus two, we just actually go to our diary.
We are not doing this many work right.
And we get the answer.
So four can return three as an answer.
Now when this five it has to get for three because it has already received the answer for four.
Next will be five two, three is not going to do all these work.
No it has this answer.
So it is just actually going to return true here.
And we will get five here.
Now next call this six is going to make for four which is the fib 251.
It has already made this time instead of doing all these work right.
All these work which four did initially, it will just write down the answer.
As we can see directly, three is returned.
No such tree is made.
And the reason is that we remember the past.
We know that.
Hey, previously I have done this kind of a calculation, so I don't think I need to do it again.
Right?
We saw the same thing in Python tutor as well here also by a tree.
It is also clear to you properly and you can see how many calls are getting overall eliminated by this
approach and thus how DP is very good concept of solving your problem, right?
So now once I have got four six, I can directly say eight is my answer very comfortably.
I can say that if I add this, this function returns eight.
Okay everyone.
So I'm pretty sure that this whole approach now will be a lot more clear.
Again, we are going to talk a lot.
DP is all about solving problems and understanding different approaches, something which we are going
to do as we move forward.
But the basic idea should be a lot clearer, and that is the exact reason I am using so much visualization,
doing each and every thing in front of you so that you understand the basic idea.
Okay, so now what I want all of you to do is to make this Fibonacci code, see how many repetitive
calls we are making.
Write this code once yourself using this diary, or even use even.
Just write it in front of you to see if you have actually calculated for that number or not.
Try to use Python Tutor to see how your diary.
This list is getting changed and you will get a whole idea.
So the exact same thing which I have taught you.
Just take 15 minutes and try to do this at your end once.
Okay, so that's the very basic idea everyone.
I am now pretty sure that deep the idea is clear.
Again, it will get a lot more clear as we do more and more question something which we will be following
in the upcoming videos.