In the previous videos, we have discussed the recursive as well as the memoization approach for solving
the question.
Minimum cost for climbing stairs.
In this video, let's get started with the tabulation or bottom up approach.
Now to discuss this approach, let's take an example.
Let's say the cost array which is given to us is this array over here.
And notice that the length of the array which is given to us over here is equal to eight.
Now, the tabulation approach is all about having a table and storing solutions to subproblems in the
table.
And then we'll use the solutions to subproblems to solve the original problem.
Now for this question, we will need a table which is of length one greater than the length of the cost
array which is given to us.
So over here the length is eight, and the length of the table that we will be using for the tabulation
approach is equal to nine.
Now why is this the case?
Let's try to think about that.
And I'm sure this will become very clear when we discuss what we are actually going to store in these
cells.
So again notice the length of this array is one greater than the length of the input array.
The indices zero up to seven account for the steps which is what is given over here in the cost array.
And then we have one additional cell over here for the destination.
Because remember when we discussed the question we had discussed that the destination is beyond the
input array.
Or we'll have to reach over here.
Or rather it's not about reaching the last index over here.
It's reaching beyond that.
So we need one cell for the destination as well in this table and in each cell in this table over here,
we are going to save the cost required to reach that particular place okay.
The minimum cost to reach that particular index.
For example, the value that we are going to store over here will be the cost required to reach the
step with index four.
Similarly, what we are going to store over here will be the minimum cost required to reach the step
with index seven.
And what we store over here will be the minimum cost required to reach the destination, which is beyond
the steps.
So this is why we need an extra cell in the table over here.
Because our aim is not just to reach the last step, but rather it's to reach beyond the last index.
It's to reach over here.
So that's why we have an extra cell over here.
So we have discussed what we are going to store in each of these cells in this table.
Now let's proceed further.
Remember in the question it was mentioned that we can start at the step with index zero or the step
with index one.
So that means that if we want to reach this step or if we want to reach this step, the cost is zero
because we can just start over there.
Okay.
So if you want to reach this step and we are starting there, then we are already there.
So we did not have to pay anything to reach there.
And remember, what we are storing over here is the cost to reach that place, not to use that particular
step.
So if you want to reach this step and you're starting over here itself, you are already here.
You have not used any step to reach over here.
And that's why the cost is zero.
And therefore we can fill the values at index zero and at index one as zero.
So these are the initial conditions.
Now let's see how we can proceed further and fill this table up.
Because if we can fill this table then we would just have to return the value that we get over here.
Because whatever we are going to fill over here is the minimum cost to reach the destination.
And that's what the question asks of us.
Now, how do we fill this value over here?
Let's discuss that.
Now I can reach this particular step.
That is the step at index two, either by taking two steps from this step or by taking one step from
this step.
So there are two ways of reaching the step with index two.
Now let's compute the cost for these two paths.
Now if I'm going from here to here the total cost involved is zero plus the cost for using the step
at index zero.
Now we have zero over here because the cost to reach over here is zero.
And then we'll have to use this step for which we'll have to pay this amount over here, which is the
value at index zero in the cost array.
And that's equal to one.
So the cost for this path is zero plus one which is equal to one.
What about this path.
The cost for this path over here will be zero plus cost at index one.
Because again we have zero over here because the cost for reaching this index is zero.
And then we are using this step.
So that's why we'll have to pay cost at index one which is two.
So the cost for this path is zero plus two which is equal to two.
And because we are asked to identify the minimum cost for reaching the destination, we are going to
store over here the minimum between these two, which is equal to one.
So I can store this one over here.
Now let's proceed and fill the value at this particular place.
Now again to reach over here I have two possible paths.
I can either start at the step with index one and take two steps, or I can start at the step with index
two and take one step.
Now the cost for this path over here will be zero plus cost at index one, and the cost for this path
will be one, which is this one over here, one plus cost at index two.
Now cost at index one is equal to two.
So that's why this is two.
And cost at index two is equal to one.
So this is one.
So the cost for this path over here is zero plus two which is two.
And the cost for this path over here is one plus one which is equal to two.
Now the minimum between 2 and 2 is two itself.
And therefore I can fill the value two over here.
Okay.
Now let's try to generalize this because I think we have traced the algorithm sufficiently to understand
how this is going to play out.
Right.
So let's write the general case.
Now if I call this array over here min cost.
Then min cost at index, I would be the minimum between the two paths, which I can take to reach the
ith index in this array.
Now the two ways are taking one step from the I minus one step and taking two steps from the I minus
two step.
Okay.
Now for taking one step from I minus one will first have to reach the step with index I minus one.
And that's accounted by this over here min cost at I minus one.
And then we'll have to use that particular step.
And for that we'll have to pay cost at index I minus one.
Similarly for taking two steps from the I minus two step will first have to reach that step.
And for that the cost involved is min cost I minus two.
And then we'll have to use that step.
And for that we'll have to pay cost at I minus two.
So these are the two possible ways for reaching the ith index.
So we'll compute these two.
And then we'll take the minimum of these two and store it at min cost at index I.
So this is how we will iterate over these indices to finally be able to fill the value at this particular
index over here.
And that would be the solution.
So finally we'll just have to return min cost at index n okay.
So I'm just generalizing it.
So if the length of the input array is equal to n then the length of this array which is min cost would
be n plus one.
And the last index over here would be n because this would go from zero to n which is a total of n plus
one cells.
And this index over here is going to be n.
And we'll just have to return min cost at index n.