Let's now write the tabulation approach for solving the minimum cost climbing stairs.
Question.
So again we are given this cost array over here.
Now let's say let n is equal to cost dot length.
Okay, now we would need a DP array, and in the DP array, every value at every index is going to represent
the cost required to reach that particular index.
Now because the question is about reaching beyond the last step, like that's something that we have
previously discussed.
Like for example, let's say the cost array has three elements.
So that would mean there is a step at index zero, step at index one and step at index two.
And the aim is to get beyond the step at index two.
Okay.
So that's why the length of this DP array is going to be n plus one.
Because we just don't need to reach the last step.
We need to reach beyond it okay.
And at every index over here in the DP array we are going to store the cost of reaching that particular
step.
And the size is n plus one.
And initially we will fill each cell in this array with the value zero.
Now again over here notice the size or the length of this array is n plus one.
And finally we will be just returning dp at n.
Again the steps range from zero to n minus one, and dp at n would be the cost for reaching beyond the
last step.
And that's what we need to find out okay.
So let's write that over here as well.
So finally we will just be returning DP at N okay.
Now to proceed we can say that DP at zero.
Is equal to zero and dp at one is equal to zero.
Now this is the case because in the question it's mentioned that we can start either at the first or
the second step okay.
That is we can either start at the step with index zero or the step with index one.
And therefore there is no cost associated with reaching those two particular steps.
And again remember in this DP array over here we are storing the cost for reaching the step with a particular
index.
Like for example, at DP at zero we are storing the cost for reaching the step with index zero.
Similarly, dp at index five, for example, would be the cost for reaching the step with index five.
Okay, so dp at zero is zero and dp at one is one.
And now we would need to iterate from two up to n.
So I can say for let I is equal to two I less than equal to n I plus plus okay.
And for each of these cases I have to calculate the cost for reaching that particular index either by
taking one step or two steps.
So again let me write this out and it will become clear.
So let's have two variables cost to come from one step back and cost to come from two steps.
Back.
Okay, now the cost for reaching this particular index, the step with this particular index by taking
one step would be cost at I minus one plus depee at I minus one.
Right.
So why is this the case?
Because this would be the cost for reaching the step with index I minus one.
And we would have to use that step and take one step.
So whenever we are using a step we'd have to pay this price.
Right.
So that's why the cost to come to the index I by taking one step would be cost.
And I minus one plus d p at I minus one.
Similarly, the cost to reach the step with index I by taking two steps from these steps, which are
two steps previous to it would be cost at I minus two plus d p at I minus two.
Okay, and then d p at.
I would be the minimum between these two because we are finding the minimum cost of climbing the stairs.
So DP at I would be the minimum between cost to come from one step and cost to come from two steps back.
Okay.
And finally over here we have already written once we are done with this, once we have iterated through
the values from two up to n, we would have calculated d p at n, and then we will just return dp at
n.
And again remember n is beyond the last step which has the index n minus one.
So when we reach the index n it means that we have gone beyond the last step.
And that's what the question asks us to find.
So we can just return dp at n.
And this should solve the question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.