Hello all and welcome back.
So in this video let us now move forward and solve some more questions on DP.
Now the question which we have to solve is a very famous question which will help us in clearing lots
of concepts when we will be dealing with DP questions in future.
The question is minimum cost path.
Now let me explain you the question.
So question is something like this.
It says that if you are standing here and let's say you have to reach to this last cell, okay, say
we are starting from here and we have to go till here.
We have to tell the minimum cost path.
Now let's say you can in a very easy manner think of these as the total or some fees which you have
to pay, which are written in front of you.
You will start from here.
You could have gone to three like this.
You could have gone like this as well.
But we have to make sure that we tell the minimum path okay, minimum path cost path where some of these
numbers is going to be Minimum.
Okay.
Seems like this exactly is the path.
If we take this path, I will be able to reach to my minimum.
Right, everyone.
So here the sum is one plus two, three three plus two, five five plus three eight.
Here it would have been nine plus three which is 12.
Okay.
So the path seems to be something like this okay.
Which is our answer.
We have to just tell the minimum cost path.
Now the question is written here as well.
So let us read this uh, because it is very important to understand if the same will be given to you
in any competition or any online assessment, how we will be understanding this one by one.
So you have a cost matrix.
Okay.
Again it is just a 2D list.
We are aware of this and you need to find the minimum cost to reach a specific position.
Now we are taking this position as three comma three.
Again we can take it as an as well.
Starting from the top left corner, which is zero zero.
Each cell in the matrix has a cost that you need to add up to get to the total cost for the path you
take.
Okay, so the path which we are taking, we have to keep on adding that cost.
You can only move down to the right or diagonally down right.
This thing is very important to understand.
It is saying that you can either move right or you can move down or diagonally in this direction.
Okay.
So this is right.
This is down and this is diagonally.
Down.
Right.
So these are just the things which we can move.
And again that is very important because if we would have moved let's say in some other direction then
our solution might change.
Right everyone.
So these are some constraints which you have to understand very patiently whenever any question is given.
Now, tomorrow, a question can ask you that, hey, you can move in all the directions.
That is fine as well, right?
Maybe that can help you to reach a solution quickly.
So just the approach will change.
But the idea, the intuition you should be forming from these type of questions.
Now this is clear.
You keep in mind that all costs are positive integer.
We are given the same cost matrix.
Here m and n are three comma three and it is asking us to minimum cost.
Okay great.
So let us see now everyone how we can reach out to this particular uh, code or the problem.
Again you have to make sure that first we write down the.
Recursive solution.
Then we see if we can apply memoization or not.
And if memoization can be applied, then we can use tabulation as well.
Okay.
So that's the approach which we will follow everyone.
Now let us see how we will majorly be solving this question.
So if I am at a particular let's say matrix let me draw it like this.
Let me draw it three cross three.
Only the one given in question.
We know that it is, in a way a 2D list okay.
So let me draw it nicely.
Here.
This is the zeroth zeroth one two.
So in terms of rows and column zero and zero we have to start from zero zero first row and first column
and reach to let's say two comma two.
In this point what should be fine right.
Great.
We are standing here.
Now let us see what are all the directions.
I can either move in this direction or in this direction or in this direction.
Right.
So let me just write it down as well.
So let us just scroll a little bit down and see directions.
In which.
We can move.
Okay.
So again first is on the right to move on the right.
What we have to do everyone I think if we have to move on the right, we can do two things.
Either we can say that hey I am on zero zero as of now.
If you have to move on the right, then your column is increasing and row is same.
Okay, so now we have to talk a lot in terms of column and rows.
These are your overall rows and these are your columns okay.
So now if we see if one has to move here, the row is same but column gets increased.
Okay.
Or we can say one more thing as well.
If we have to reach here, then let's say I started with m n which is three and three.
We can just reduce this n by two okay.
So I will repeat this again.
What exactly am I saying.
We are starting from, uh, zero zero.
Okay.
Now, if I have to move in this direction, then N and M are my values where I have to reach.
Can't I say here that.
Hey, I am moving a step closer to my column because this is n minus one, right?
Because if my m this is three comma three.
Okay, then I can say this m and n here when I move with respect to this final location, n is going
to be two because I have to subtract one from that.
Okay, so when we will write this in code, it will become a lot more clear, just a different way of
thinking.
You can either say that hey, I have to go 100km.
Let's say if you are standing here, okay?
And this is the destination, which is 100km.
This is your destination.
Final.
Now, either you can say that.
Hey, when you are standing here, you can say that.
Hey, I have walked 20km or I have covered 20km.
Or you can say that.
Hey, I am left with 80km.
Now first approach.
You must have done a lot of times in many questions in this course as well.
I want to make sure that you understand using second approach as well.
Okay, great.
So yeah I think that is clear.
Now everyone this is where we have to apply for.
Right.
So we have to make it zero comma one.
Second is down When we have to go down, that means we have to increase.
The row and column will remain the same.
See, we are standing here.
If we have to go down, increase the row.
But this column is zero only.
And when we have to go diagonally, then third diagonally.
Both of them have to increase.
Okay.
So great.
Cool.
So now what we will do.
What is the overall intuition.
Now once we have written all these things see we will just call recursion on these paths and say that
hey get me the cost.
If I am taking left top down or a diagonal step, recursion will get me the cost and I have to make
sure that I take minimum of all these cost and add the cost where I am standing, and I will get my
answer okay.
so the question will have to do the major work.
We just have to make sure that once we have all the cost.
Because if you think in a way, I can just divide this question like this.
What if I start from here, then how much?
Uh, let's say, what is the cost?
What if I start from here?
Then what is the cost?
And what if I start from here?
Then what is the cost?
If all these costs are given to me?
If I get the answer for all these cost, then I can just add minimum of add my cost to the minimum of
these three.
We just have to handle one case.
That is, if you are standing here, either we have to make sure that we don't make this call okay.
Because here we cannot go right.
This is out of our grid, or we have to make sure that we either return some very large number like
infinity, so that when we take the minimum, this whole thing is eliminated.
Okay.
So I will repeat it again.
Let's say when you have reached at this particular position, either don't make this call, check if
where you are standing.
If it is uh, Basically in the overall if it has a right step or not.
If it is possible, think of it as a mountain.
If you are standing on the cliff of a mountain, of course you cannot take a step.
Okay, so either don't take the step or just look down and see that, okay, it is very deep.
So either we will repeat that.
Hey it has an infinite cost here okay.
So even when I get the answer as infinite I will not be taking this in my final answer.
Okay everyone.
So pretty sure that the question and the intuition is clear.
So what I want all of you to do now is in your, uh, coding exercise, try this question out first
by just writing the recursive code, something which we will discuss in the video.
And then going forward, we will see how we can write the code for other overall memoization and DP
technique as well.
And if they will be applicable, uh, or not.
Okay.
So great everyone.
Uh, let's meet in the next video.
Till then, please make sure that based on our discussion, you are able to write the overall recursion
code for this problem.