In the previous videos, we have already discussed the recursive approach for solving the minimum cost
climbing stairs.
Question.
Now over here, let's see how we can memorize this.
And again remember the memoization approach is also called the top down approach.
And this will significantly improve the time complexity.
And the good news is that we can do this by just adding a few lines of code.
Now to discuss this approach, let's take an example.
Let's say this is the cost array which is given to us.
And over here we notice that we have the indices starting at index zero going up to index seven.
Now in the recursive approach, because we did implement the recursive solution starting at index zero
and going to the last index.
Remember we had discussed that we have to calculate both cost from zero and cost from one.
And then we would return the minimum among these two.
And this is the case because we can either start at index zero or start at index one.
Now let's quickly draw the recursive tree for one of them.
And this is just to see that there are in fact overlapping subproblems, which makes a strong case for
memoization techniques.
Right.
So we start at cost from zero.
And then we would call cost from one and cost from two in the two branches because we can either take
one step or two steps.
Now if we reach the step at index one again we would have two branches cost from index two and cost
from index three.
This is taking one step and this is taking two steps.
And it goes on in this manner.
Now over here, if we reach the step at index two we would again have two branches and cost from index
three.
This is the case where we take one step and we would call cost from index four.
This is the case where we take two steps.
Now over here notice that we are calling cost from index two over here as well as over here.
So we have overlapping subproblems.
Similarly when it comes to cost from index three notice that we have it over here as well as over here.
And this makes a strong case for memoization.
Because if we just store these values when we compute them we could have avoided computing this again.
Right.
We could have just returned the value because we have already computed it probably over here.
Now in this question we can use a hash map or a simple array for storing the costs that we are computing.
And again, let's say we are just doing it with an array.
So how would it look like.
So because we have seven indices over here, we would need seven places in this array where we are going
to store the costs.
And then at every place we are just going to store the value that we get over here.
So cost from zero would be stored over here, cost from one would be stored over here.
And it goes on in this manner.
Now again we are not going from 0 to 1 etc. like we would do in the case of tabulation.
What we are doing over here is whenever we get a value, like for example, let's say there were just
four elements.
So let's say this is the cost array which is given to us now over here when we come to cost from index
three.
Right.
So that's the last element.
So there would be just one way of reaching the top right.
And we could get the value.
So in this case if this is the input array cost from index three would be taking one step from this
step over here.
And the cost for that is three.
Right.
So when we compute it we are just going to directly store it over here.
Let's say hypothetically in this example it's three right.
So if this was the cost array and the cost from going from this index to the top would be three.
So we would just store it over here.
Or if this itself is the array which is given to us, we can compute the cost for reaching the top from
index seven.
And that would be just one because we just take one step right.
So this is the last step.
So we would directly compute it and store it over here.
So whenever we are able to compute the cost for going from a particular index to the top, whenever
we get the value, we will just store it in this array.
And then in any branch or in any recursive call, before we go ahead and compute the cost for going
from that particular index to the top, we will check whether we had previously computed the cost,
because if we did compute it, we would have stored it in this array.
And we will just retrieve it and return it without recomputing.
So that's the memoization approach.
And again, as we always do with memoization over here, also, we will just initially fill all these
cells with minus one.
And that will help us to check whether we have computed the value previously or not.
Because whenever we have cost from a particular index, we will check whether the value at that particular
index in this array over here is minus one or not.
And if we see that it's not.
Minus one.
We will not go ahead with any computations, but rather we would just retrieve that value and return
it.
On the other hand, if we see that the value at that particular index in this array is minus one, then
we will go down the recursive tree to compute its value, and before we return it, we will always store
it in this array over here.
So that's the memoization approach for solving this.