Hello all and welcome back.
So in this video let us now move forward and write the code for the question minimum cost path.
Now we have discussed this already in the last video.
And in this video I want to make sure that we are able to write a recursive solution for the same.
Okay, so as discussed in the last video, the problem is something like this.
We are given a matrix which has a path.
Overall we have to follow starting from zero comma zero and we have to reach, let's say 2MN or the
bottom right okay.
So the right most and the bottom most cell.
Now normally we can do it either by incrementing this starting point or by decrementing the last point
I am going to do it by decrementing our m and n.
The reason normally the other one is pretty easy, but I want to make sure that you are able to understand
each and every approach.
Okay, so the same will become a lot clearer when I will write the code for this.
It is based on our discussion only, so don't have to worry on anything.
Now let's go back to the quotient statement.
What we were given.
So it was something like this.
We are given a cost matrix.
Now the shape is three cross three.
But because of zero indexing we know that m and n will become two comma two.
Now you are passing minimum cost path recursive and m and n here.
If we do it in other way we have to normally pass I and J as well, which will be zero and zero right.
So I am just going to show you another approach through which we can avoid that.
Okay great.
So let us now write the code for this one.
First the base case okay.
Which we will come back to I think recursive call is something which we discussed.
So let us write down the recursive call first.
And then we will write our work and return the answer.
Let's talk about the recursive call.
We saw that how we have to make these calls in the last video.
If we are starting from here okay.
All I am now asking you to do is just to solve it in another way, through which it is a lot more clear
as well.
Let us, instead of starting from this position, let us start from the last position that is M and
N.
Now if we are starting from m or m and n, which is two, comma two or any other cell as well, we have
to make sure that we reach to zero comma zero okay.
Again the other approach is easy.
So please make sure that you understand these approaches as well.
Coding and DSA is more about understanding different different approaches as you code.
Now the whole discussion stands as it is just that I will be making three steps which will be in the
different direction.
Okay, so here my steps are left.
Then I have right.
Oh sorry.
Not right.
My bad.
Left.
And then we have top.
Okay so let me just remove this.
Second after that is top and third one is diagonal.
Okay everyone.
So pretty sure this must be clear.
Now for doing that.
Let us see what exactly we have to do.
First is cost left.
It's going to be equal to min cost path recursive cost matrix as it is if we are moving to left row
will remain as it is.
M here is equivalent to row, but the column is going to decrease by one right.
So in the right row was remaining.
The same column was increasing by one.
If I have to go here, Rho will be two only.
Column will become one.
So I have the cost from left.
Then cost top.
Mean.
Cost path.
Cost matrix.
This time column will remain the same, but Rho will get subtracted by one.
So if I am moving on, top column is two only.
But this rho will become one.
Okay.
And the last thing is cost of diagonal, which again will of course be equal to cost.
This time just subtracting both of them.
Okay.
So just I am starting from here and reaching to this zero comma zero.
Once I have this cost, what I have to do, everyone I can just say answer equals cost of m and n where
I am standing plus minimum okay.
And I think Python minimum takes more than two as well, so we can just use it as it is.
Cos diagonal and cost top.
Okay so yeah it's not giving any error in many languages it just takes two argument.
So we have to call it multiple times.
Okay great.
So I'm pretty sure till now everything will be clear.
I have just tried a different approach starting from here and trying to reach here instead of the other
way around.
Okay, the benefit you can think that it help us to not pass IJ as well, or the starting point as well.
Okay.
Which we will be increasing.
So I believe that it should be very much clear to use different approaches.
Great.
Now once this is clear let us talk about the base case.
What if we start or we reach this particular position, the origin from where we have to start?
I think we can just here return that.
Hey, where you are standing, that is your cost.
Okay, so because both of them are zero, right?
So let's say if I want, if I have reached here or if I want, if I start from here only then you can
say like if it's a single element matrix, then again we can just stay here and get our work done.
Okay.
Get the cost.
Great.
So all this is fine.
But if you remember, we also discussed another approach in the another outlier in the last overall
video, which is that what if I'm standing here?
I cannot go to these directions.
Right everyone.
Similarly, when I start in this particular matrix, let's say if I'm standing here, I cannot go in
these directions.
And I'm pretty sure you will be able to see what are the constraints here.
My M and N they are becoming less than zero.
And if I am going to less than zero, either I can stop that.
Either I can say that hey, don't go here or I can say that hey, you are getting a infinite cost here.
Everything outside of this matrix is infinity because we are solving for minimum cost.
We can take infinity in quotients where you have to give for maximum cost or something.
You can take the negative infinity.
Okay.
Great.
So let us see that everyone what I'm saying here, all I'm saying is if m less than zero and n less
than zero, we can just return float of inf.
Right.
Something this we have already discussed in one of the questions how this is the maximum number basically
which Python allows right.
Infinity.
So in other languages like C plus plus Java we have int max or something.
So again you can take any very big number as well.
That should be fine.
And now I think we have handled all the cases.
The other approach I was saying was something like this.
So if your M equals zero then we will be avoiding these two calls.
We will not be making these two calls okay everyone.
So you can handle it like that as well.
But it will give you lots of conditions.
And my aim is to showcase you different approaches and this is a smart approach.
Let your overall metrics go there.
That should be fine.
But we can say that, hey, this is an infinite cost and once it reaches here, let's say then we will
not make other calls because we are returning from here already.
Okay.
So yeah, I think this code should overall work.
The answer should be if you start from here three then the minimum is two.
Then this is two and then one finally right.
So let us run this and get the cost.
The answer should be three plus two, five plus two, seven and eight.
Okay.
So it's giving us an error.
Let us solve that recursion.
Okay.
It's saying maximum recursion depth exceeded.
Let us see why is that.
Okay.
So we have not returned the answer right.
So we have to return the answer as well.
Okay.
So still it is giving the cost.
Maximum recursion depth is exceeded.
Let us quickly see where exactly have we made an error.
So we start from m equals zero.
And if they are zero then okay.
So it should be.
All right everyone either m is less than zero or n is less than zero okay.
It is not.
And because else the call will get keep on getting made just because we have less conditions here,
it was easy to, uh, easily see that.
Yeah.
This is where error is getting.
And we have the answer minimum cost to reach two comma two using recursion.
Is it?
Okay.
So pretty sure this approach is clear to each and every one of you.
Again, if we have to do it another way you can take IJ.
But I think this is a better approach and overall a smarter way of solving this problem.
We are making sure that we are handling all the cases like this.
We have the base case here as well.
And all these are the recursive call which we will be making.
And then you can get the cost here.
Now what I want all of you to do is if you are not able to solve it, please try to write the code recursive
code yourself even if you were able to write the recursive code in a different approach.
When you start from zero comma zero, please make sure that you write this code as well at your end.
Okay, again, the basic idea is to make sure that you understand different approaches.
So if tomorrow you see some other code which is being done by a different idea or approach, you are
able to understand that as well.
Okay, so great everyone, if you are able to 100% understand this thing, then next step, you know
we have to apply memoization here.
Now why we have to do that?
Because if we see okay for this particular let me just get this image.
So for this particular matrix we will be making lots of calls which are repetitive.
How repetitive.
Pay attention when I'm here when I'm on this tree okay I will make a call to this.
But five will also make a call to eight, right?
Then one will make a call to four.
But this eight will also make a call to four.
Right everyone.
So you can see that how many calls we are repeating.
For example for
123482153.
Now this three will make calls here.
This five will make calls here.
So we can see that okay eight we are making multiple calls.
And again as the metrics will increase these calls will just keep on piling up.
And we have we will be making lots of calls.
But I feel that we should have saved it somewhere that hey, this is the maximum.
This is the answer.
If I'm making the call from here, this is the minimum cost which I am getting.
Once you have saved that, I think it is very easier to not make those calls again.
Now this is very much different.
Normally it is known as two dimensional DP because this is in some way we are not dealing with a list
or.
A element in a straight line.
Here we have a matrix instead.
Okay.
So to just give you the idea what you can do here, you can play on indexes.
Okay.
So this time it will be different from all the questions which you have already.
Which we have done previously.
This time we have to create a matrix or a 2D list okay.
In this 2D list we will be saving our answer like this.
Now we are saying that okay we.
Are starting from here.
What is the cost?
If I start and end here, I think it should be cost of m and n each of this matrix.
Each point in this matrix will define cost to reach.
This point.
From m comma n.
And of course, since we are dealing with the minimum cost.
Right everyone.
So we will get the minimum cost to reach this point from a point.
From this particular point, this is how our matrix will be defined.
Now I want all of you to first try this out once because again, this question you will be doing or
you will be entering into this 2D deep domain for the first time.
So I want to make sure that each and every one of you understand this thing, right.
I have just flipped that we are starting from RN, not from zero zero.
Apart from that, everything is same.
Okay, in the next video we are going to discuss that how exactly we will write a memoization approach
for this code.
So let's meet in the next video everyone.
Till then please make sure that you try this question out again.
And now try to write the Or change your recursive code into a memoization approach.