Previously, we have discussed the recursive approach for solving the Fibonacci question.
In this video, let's get started with the memoization approach or the top down approach for solving
this question.
Now remember memoization is just recursion plus storage.
So as we have already written the recursive approach of solving this question, we just need to modify
it a bit to ensure that we store what we compute.
So you will see that we will just need to add a few lines of code to the solution that we have already
written to come up with the memoization approach.
So let's get started.
So over here we have the recursion tree for finding f of five that we have seen so many times.
Now what we will do is we will have a hash table or a dictionary.
And whenever we need to find let's say f of five or f of four or f of three, what we will do is before
we go ahead and recursively call the same function with lower input.
First we will check whether this value that we need is there in the dictionary or hash table.
And if it's not there, then only we will compute it.
And once we compute it, we will store it or add it to the hash table.
So this is the approach that we will take.
So initially we are trying to find f of five.
So let's trace the algorithm.
We will check whether f of five is there in the hash table.
And we will see that it's not there.
If it was there we would have just returned the value.
But again we are just starting out.
So because it's not there, we will go ahead and we will find F of five by finding f of four and f of
three.
And once we get the value, we will store it in the hash table.
So let's draw the hash table over here.
Initially notice that in the hash table we will have the values zero and one for n, because these are
values that are already given to us.
In the question, we know that when n is equal to zero, f of zero is zero, and when n is equal to
one, f of one is one.
So these values are already there in the hash table or the dictionary.
And then we proceed.
We are calculating f of four.
And again we'll check is f of four in the hash table.
It's not there in the hash table.
So we have to again go ahead and calculate f of three.
We will see whether f of three is in the hash table.
We see that it's not there in the hash table.
So we go ahead and calculate f of two.
Now we will check is f of two in the hash table.
We see that it's not there in the hash table.
So we proceed down this branch.
We go to f of one and we'll check is f of one in the hash table.
And we see that yes f of one is there or n is equal to one is there in the hash table.
So we will just return the value one.
So this over here will return the value one.
And then it will go down this branch.
So we will check f of zero and we'll see that it's also there in the hash table.
So this also will return the value zero.
Now we get the value of f of two because we have the value of f of one and f of zero.
So we add these two together to get zero plus one which is equal to one.
So f of two is equal to one.
And once we have computed this we will store it in the hash table.
So over here for n is equal to two the value is one.
So we store this.
Then this over here will return.
And then when this branch is explored for F of one, we see that we already have this value, and therefore
this will return the value which is one, and thus f of three is calculated which is one plus one,
and that's equal to two.
So we get the value of f of three as two.
And we store this.
In the hash table.
So we have over here for n is equal to three the value is two.
And then this returns okay.
So this returns the value two.
And then we explore this branch over here and over here.
We just want the value of f of two.
So we want the value of f of two.
But notice that we already have it.
So we don't need to go down these paths.
We can directly return the value which is equal to one.
So this over here will return one.
And in this manner we will be able to calculate the value of f of four which is two plus one which is
three.
And once we get this we store it in the hash table.
So we have got the value of f of four as well.
And this returns the value three.
And then when we go down this branch and when we try to find the value of f of three, we see that we
already have it in our hash table.
So we will directly return the value two.
And thus f of five will be calculated, which is.
Three plus two, which is equal to five.
And once we get it, we store it in the hash table.
So notice that because over here we already had calculated f of three.
We did not have to do these calls.
So this is why memoization has much better time complexity than a simple recursive approach.
So this is how it works.
And we were able to find the value of f of five.
Now the good thing over here is that we are able to retrieve a value from the dictionary or hash table
in constant time when we have the key.
So for example over here for f of three the key is three.
And because we have the key we can access the value of f of three which is this value over here which
is two at constant time.
So this is what helps us to significantly improve the time complexity.
Let's now go ahead and code the solution that we have discussed over here, which is the memoization
approach.