Welcome back.
To start with, let's make a few observations to develop the necessary intuition for solving this question.
And for this, let's make use of the example which is given to us.
So if there are three elements in the cost array which is given to us, and if the costs are one, two
and three, we have seen that the expected output is two, because the best path or the path which involves
the minimum cost for reaching the destination, is by starting at the step with index one and then taking
two steps to reach the top or the destination.
Now notice that over here the destination is beyond the given array.
So this is an important thing to note over here.
And that's why it's very important to take a look at the examples given along with the question when
you are dealing with a coding interview question.
So the examples given are always very helpful and very important.
So the first observation that we have made over here is that the destination is beyond the given array.
So we don't just need to reach this index we need to reach beyond it.
The second thing that we can observe in this question is that it's mentioned that we have to pay to
use a step, okay.
So if I want to use this step I have to pay.
And if I do pay, I can either take two steps or I can take one step.
All right.
So these are the important things to note or observe in this question before you go ahead and solve
it.
Because if you don't do that you will end up writing something which is not what the question demands
from us.
Now, to solve this question, first let's write the recursive approach, and then we will memorize
it by just adding a few lines of code.
And after this let's write the bottom up or tabulation approach.
So let's get started with the recursive approach.
And for discussing this approach, let's take the example where the cost array is one, two and three.
So the indices are zero, one and two.
And we will be writing a function which we will be recursively calling.
So let's call this function cost from and to this function we will be passing the index as an input
parameter.
Now before we write this function, let's take a moment to discuss what this function actually will
return.
So cost from this particular index over here will return the cost of reaching the top from this particular
index.
Now again over here we are writing the recursive approach.
And you can write recursive solutions either going from index zero to the last index.
Or you can go from the last index to zero.
Now over here.
Let's go ahead and discuss this approach where we are starting at index zero.
And we will be going to the last index.
But it's always good for you to practice and write both the approaches.
So let's just continue with the approach where we are starting at index zero.
And in this context, cost from index will return the cost of reaching the top from the index at hand.
So this is the definition of the cost from function.
And after we have written this function, we would just have to finally return the minimum between cost
from zero and cost from one.
Because in the question it's mentioned that we can either start from the step with index zero or the
step with index one.
So if we start at the step with index zero, then we will call cost from zero.
So this over here will return the minimum cost for reaching the top starting at the step with index
zero.
And again this is the minimum cost.
Okay and cost from one will return the minimum cost for reaching the top when we start at the step with
index one.
So this is how we are going to implement the recursive function.
Now let's discuss how this function over here can be written.
Now again let's make some space over here.
And we have seen that we will finally call cost from zero and cost from one.
And the recursive tree for these two will follow a similar logical approach.
So for our learning purpose, let's just write this recursive tree over here, which is cost from index
zero.
Now this over here means that we are starting at the step with index zero.
Now we know that when we start at a particular step, we can take two possible approaches, which is
that we can either take one step or we can take two steps.
But in either of these cases, we are using this particular step over here.
And remember in the question it's mentioned that whenever we use a step we have to pay for it.
Right.
And over here the cost for the step at index zero is equal to one.
So that's why we'll have to pay one in either of these cases.
So in either of these cases I will have to add one.
And over here if I'm taking just one step when I'm starting from index zero, I would reach the step
with index one.
And then I would have to add to this one over here the cost for reaching the top starting at index one.
So for that I would recursively call the cost from function again and pass one as the input parameter.
And in this case, if I'm taking two steps and I'm starting at the step with index zero.
So when I take two steps I will reach the step with index two and two.
This one over here I'll have to add the cost for reaching the top starting at the step with index two,
which can be obtained by recursively calling the cost from function and passing two to this function
over here.
So these are the two branches that the recursive algorithm will take.
And then it will just go on in this manner.
Right.
So over here again we would use this particular step.
And there would be two branches.
The branch where we take one step and the branch where we take two steps.
And it goes on in this manner.
So I think this is pretty straightforward.
And there's no need for us to draw the complete recursion tree.
So this is the recursive case.
Now let's also discuss the base case for the recursive solution.
So what would be the base case.
Now always remember the base case will vary depending on whether you're going from zero to the last
index, or whether you are writing the solution in a way that you're starting at the last index and
going to zero.
So in this case, because we are going from zero to the last index, we would hit the base case or the
terminating case when the index that we are passing to the cost from function is beyond the last valid
index.
So in this case the last valid index is n minus one, where n is the length of the cost array.
So if the index is greater than n minus one, we know that we can stop.
And at that point we can just return zero.
Now the reason why we can return zero is that because we have reached beyond the last index.
And remember we had discussed that our destination is beyond the last index.
So if the index is greater than n minus one, it would mean that we have already reached the destination.
And that's why the cost would be zero.
And that is the reason why we can return zero if index is greater than n minus one.
So this is the recursive approach for solving this question.
We have discussed both the recursive case as well as the base case.
Now all that remains is to discuss the complexity, the time and space complexity of this approach,
as well as to implement the code of this approach.
Let's do that in the upcoming videos.