Hello all and welcome back.
So in this video let us now move forward and try to do the minimum cost path question, this time using
the tabulation.
That is the pure DP approach.
Now this will be the first time you all will be attempting a question in 2D DP with this approach,
the tabulation approach.
So it is very important to understand that how exactly we form our solution here.
Okay.
Basic idea and the requirement.
You should completely understand the recursion approach as well as the memoization approach.
Okay.
We have discussed them in length in the last couple of videos.
Now in this video, once we discuss the tabulation approach, you will have lots of idea that how exactly
we are able to reach questions like these.
And then moving forward, the practice question which we have given you can do.
Based on this understanding, though, solutions for those questions are given, it is very much expected
that you understand them from scratch so that you can do the same in your overall, let's say, any
particular interview.
Okay.
Great everyone.
So let us start then.
Uh, let me just draw out the matrix.
We are given a matrix like this here.
Now we discussed in the last video that how exactly this matrix will get filled.
Right.
What are the different different uh, subproblems which we are facing.
Let me draw it like this.
So yeah we saw that for example first we are on two two.
It will make a call on its left.
Right.
So if I just write down the rows and column as well on the left the call is going to be on uh two comma
one.
Okay.
Then this will make another call on the left.
It's going to be two comma zero.
Now in these kind of questions because we have to do each and everything iteratively.
There is no recursion, no as such base case or condition which you can apply.
We have to see that what are the subproblems which can be solved without any dependency?
Now, if you remember in the memoization approach, there were some problems which can be solved without
dependency.
And for some we have to make these calls, right.
The idea again is same, just that it requires a great in-depth knowledge of recursion concepts or overall
each and every concepts which we have studied with respect to recursion list 2D list.
And that is where most students face the problem.
Now from the starting in this course, we have made sure that we are discussing each and every thing
in complete depth.
And the reason is that now all of them gets bind together and gets useful while we are doing these kind
of questions.
So pay attention everyone, what exactly we are going to do?
We have to make sure that somehow we can fix, we can fill in the values where no dependencies are there.
Okay, great.
So if we even follow our overall this particular question, then you can see that now it's going to
make a call to two minus one which is here.
But again in recursion or sorry in tabulation.
We are not making these calls okay.
We have to rather avoid making these calls and check that, hey, you should not be making any call
or asking for the value there, because that would be a problem that would just give you the answer
which will be not present.
Okay, great.
So instead of this call, because we will not make it and we can take it plus infinity, we will now
go on top.
Okay.
So next call will be somewhere on.
Zero comma.
We have to just change the one minute.
So we have to change the row.
So one comma zero.
Okay.
Now one comma zero will again.
This particular node will again make the call here, which will be we have to just subtract one comma
minus one.
Again it will get minus plus infinity.
We will see either we will have a if condition to say that okay get plus infinity.
Or we will try to avoid this particular call or particular feeling altogether.
Now next is where the first value will get will get filled.
And that actually will be going to your base case only.
So we know that this is my base case.
If I am starting from this one, and I have to reach on this one as well, then the minimum cost, the
answer is going to be one here.
Okay.
Once we have filled this particular value okay.
Then I feel that we can fill other values as well.
What are the other values.
So pay attention.
This overall node or this sub problem.
It depends on these three problems right.
We know these two are not relevant.
So just using this problem we can fill this as well.
Then we can fill this as well.
Okay great.
Similarly we can now do this problem because it will depend here.
Uh, not in this one second.
Yeah.
It will depend on this and this.
Okay.
We have the values of them.
No value or one minute.
Okay.
It will depend here as well.
Right.
So let us see what is the next one we can fill when we have filled those values.
Okay.
So let us fill that.
Only the matrix was like this
123482153482153.
Great.
Now let us talk about this, uh, zero comma one.
This particular sub problem, it will depend on this this and this okay.
These are the three direction which we have took.
Now other two are not relevant.
So just basis on this particular problem I can write down my answer which is going to be five Okay.
Similarly here I can write down six because this particular subproblem will also be dependent on just
the top node.
Now if you will see, the whole approach is to make sure that those subproblems, those overall cells
which have their dependency fulfilled, let us just fill them okay.
Now we will not be making the calls, right?
No recursion is going to get going to get used here.
But the understanding is coming from recursion only.
And that's why we in the last video we understood that how exactly the order in which these cells will
get filled.
Okay, after that I believe this cell can get filled because it has dependencies here.
Okay.
And we can see these two are not the dependencies which I want.
So you will be seeing one more thing that we are filling our overall dp dp array in this way right.
DP matrix in this way.
So once this gets filled everyone it is going to be three.
Then this particular subproblem can also be done because it has dependencies on these three.
The idea is that I should be filling in the cell the subproblem where I don't have any dependency,
just that is my idea.
Nothing else.
Right, everyone, if you are able to do that, that is where you can just work on because the answer
is pretty straightforward.
You don't have to worry about anything there.
It is just that if you have done this thing, if you are able to handle each and every subproblem,
then you have the answer.
Just take the minimum and add your cost to it.
So now this particular can get filled because this right.
And you will see that in our code as well.
This is the order.
Each and everything is going to get filled here right.
So once this gets filled then it's going to make the call like this okay this has been done already.
So we will make the call above.
And finally this will start getting filled.
And once we do this filling properly, Once we are able to solve each and every subproblem, fill in
the cell value, we will finally reach here where we can just return our answer.
Okay, so great everyone!
Now let us see how exactly this will get filled.
Here I know the minimum is this.
This is the one.
So for this cell we have three dependencies.
I can write nine here okay.
Similarly I can write ten here.
Now all the dependencies of this subproblem is fixed okay.
So here I can just directly write six.
Then out of these two it is five two from here.
And minimum is three here okay.
So I have to see these three one.
And finally here I can say that eight is the answer because this five nine and ten eight is five is
the minimum and three is the cost.
Okay.
So pretty sure that you will be able to understand this.
I will highly suggest to see this part again and repeat the process.
We are just trying to fill in our DP matrix based on the cells or the sequence such that every subsub
problem or cell has its dependencies solved.
We will start with a base case.
On that base case, some things will be there which will be dependent on that right.
Once that is done, once that is done, then we can work on other part as well.
Just one thing I would like to show you here as well.
So let me just copy this particular cell a particular diagram.
So let us just copy this and paste it here okay.
Or rather uh bring it on here.
I just want to show you that how this sub problem thing is getting done.
Okay.
And this approach will be a lot helpful in many questions as well.
So pay attention everyone.
If you see if I just get this particular part out of my matrix, then I can write like this.
Okay.
Similarly, the part the first column I can get like this.
Okay.
Normally in these type of questions, when you are applying tabulation, you will either be going like
this okay, or you will be going like this depending on what call you have made first.
Okay.
In this question we made the left call first and then it started going upwards.
So this is how we are solving all the things okay.
Now pay attention.
Let's say I am just given this particular matrix okay.
So my cost matrix let's say was would be just a 1D kind of a matrix.
Then you will see one thing I know the cost here which is one.
Now this particular cell it though will be dependent on three direction.
Two of them are not possible.
So I can easily fill each and everything here in a similar way.
This particular cell, though it will depend on three, uh, values.
Okay.
It will be depending on three values.
The other two are not possible.
So I can easily fill in this.
And once I am able to fill these two because I know there are no dependencies.
Okay, I will repeat from start if I get this whole row out and if I get this whole row out independently.
Now why am I doing this?
Because this approach you will be using a lot whenever you do a 2D kind of a question, I have to show
you that these boundaries, okay, they have the least dependencies in terms of your overall matrix
or a 2D question, because values are values are not possible here.
Values are illegitimate here okay.
So we will see that these values are not possible.
These values are not possible here.
Similarly here these values are not possible.
So just a single dependencies is there which is your base case.
Right, everyone.
And this implies that we can fill the boundary.
Values easily.
Once you have done that then this particular value let's say this one, it will depend on three values
which is this, this and this.
And you have fill in all those values.
Right everyone.
So here the understanding goes a little away from how recursion was going to do things here.
You have to do all each and everything from using iteration okay.
So great everyone.
Now let us try to write down the code.
And I'm pretty sure that it will become a lot more clear.
Just a caution that if you are understanding this for the first time, please see these videos at least
2 or 3 times.
It took me a lot of time as well to understand that in depth.
Same.
I am trying because I was not able.
No one explained me with this much depth.
Same.
I am trying that you all are able to understand in the first go and then when you do the questions you
will have lots of practice.
Okay, cool.
So let us now do this everyone.
Uh, this is your tabulation approach, right?
Doing this iteratively.
Getting away from recursion as well this time.
So def min cost path memoization.
Okay.
Let's say cost m n and dp.
So this time let us send the DP instead I can make DP here which is going to be like this.
We take it zero.
The reason I think all of you know now that we have to add these things, right.
So zero is a safe option.
Instead of memo I will just pass DP here and let us call the tabulation one.
Okay.
Have we defined this.
Yeah.
So let me define this as tabulation.
I am just passing the DP from outside.
You can even have it inside as well.
That should be fine.
I want to actually show you by printing that we will get the same answer.
Okay, let us save this as well so we can compare it.
Good.
So now what we have to do everyone, once we have this thing, let us now try to code down the solution
here.
Let us have some extra space.
So you just see the solution.
Great.
So yeah pay attention now everyone.
First I think we can fill in the base case that is DP of zero comma zero equals cost of zero and zero
okay.
Pretty straightforward I don't think we have to do anything here.
Great.
Now what we have to do pay attention I can write a loop for I in range M plus one For J in range N plus
one.
Okay, I have to do something great.
If we want, we can just do this in this particular loop as well.
I can just say that hey if my I and let us take it row and column so that it is a lot more clear to
you.
Row is m, column is n.
If row equals zero and column equals zero then we know what we have to do.
DP of I row and column equals cost of zero comma zero.
We could have write written a comma zero comma zero.
Or we could have written row and column as well because both of them are zero.
Great.
Else.
Okay.
Else.
First let us try to get the cost of lift.
Okay.
What will be the cost of lift?
We know that it will be if I want to go left.
If I want to.
Let us see here.
If I want to go left.
Let's keep the row as it is.
Just decrement the column.
Okay.
Which means d p of I j minus one.
Okay, that is fine.
Everything.
Okay, let me make it row and column minus one.
Okay.
So all is good here.
No worries.
But there is a problem.
If r j is greater than zero, then only I can do that okay.
By j I means.
So we are moving to the column right.
So if our column is greater than zero then only I can do that.
Even if it is zero then the problem is that it will become minus one.
Else we can say that okay, it is float of infinity.
Okay everyone, I hope this is clear.
I will just explain it here as well.
What I meant by this particular statement.
So this is a shorthand if statement.
Pretty sure you must have learned about that here.
This is the value.
If the statement is done.
Else we return this value.
If I am here and I want to get the left value, I will just go here.
Then I will go here.
But if the j is if the column okay.
If the column is not equal to zero, then when I do column minus one I will reach here, which I should
not.
Okay great.
So let us remove this similarly constant of oh sorry cost of top.
Now this is very much straightforward with your DP solution.
So that's why I'm writing it like this.
Row minus one and call same condition if row is greater than zero else float infinity okay pretty sure.
Now most of you must have understood this diagonal equals DP of row minus one.
Column minus one.
If this time we have two conditions right.
So if row greater than zero and column greater than zero.
Else.
I have just changed my overall recursion into a iteration.
Nothing else you have done.
Once I have these three values then I can say dp of I comma j equals cost of I comma j.
Again that cost we have to add plus minimum of cost diagonal cost top cost left okay.
So let us try to dry run this and see how exactly our DP array will fill.
So pay attention everyone.
Let's say we have this particular as a DP array okay I will be starting from row and column.
Row zero.
Column zero.
Okay, so this I can just write one.
Right now if you will see row will remain the same and column will increase okay.
So I am filling in this manner I am overall filling here in this manner.
If we would have done the opposite where we must, we would have.
If you want to go in this manner, then we have to make sure that row changes in each and every loop,
so we have to keep the loop inside it.
So pay attention.
First I fill in the one because row is zero, column is zero okay right.
Next when I will come here the value is row is equals to zero.
Column equals one.
Because now the column value will start from zero and go all the way till two.
Right everyone.
because two is the N or two is the N and two plus one is three.
So this for this value you will see one thing.
We will not be getting these two values.
No they will be coming out to be plus infinity.
Because this condition is false.
Rho is not greater than zero.
But we will get the left value.
And what is the left value?
All of us can see in front of us.
This is the left value.
Right everyone.
So by just setting our constraints, I am able to say that okay, get these values and we can now just
directly do and fill in that value.
So what was the this two right.
So I can say that okay I get the minimum overall as minimum is two.
My value sorry minimum is one.
My value is two.
So please write three here.
Similarly.
Next this will get filled.
We will just get the left value okay great.
Now when we move forward okay we will go to second row.
For this, we will not get these values because this time column is zero okay.
But top value we will be able to get because this time let me just draw it again one minute.
Yeah.
So for the second iteration what we have to do everyone see we have fill in one, three and six here.
This time row is one and column is zero okay.
We will not get the left.
We will not get the diagonal.
But this top is something which we will be getting top I have a value okay which is one.
So I will get the minimum as one because this will be one infinity infinity cost I j or cost row column.
I will just add to it.
It will get filling like this.
Finally, we will fill our whole deep matrix and our answer will be kept here which we have to return.
Okay.
So let me do this.
Let me just show you that as well, everyone.
Uh, we can just have it as row call.
Row, call.
Great.
Now, what we can do, once this all is done, return p of m and N.
Great.
So let us try to run this.
It's giving us an error.
Name DP is not defined.
Okay.
We have not passed DP from here.
Uh, okay.
So it is saying minimum cost to reach two comma two using recursion is eight.
Everything is minus one.
Because we should put in DP here and see now 1365956 ten eight.
Exactly the same metrics, right?
If you want to do it the other way around, the one we discussed.
Just uh, let me just write it.
It's, uh, comments here if you want to do it in other way round.
And that is the reason I explained you that either we go in horizontal direction or vertical direction.
Just do it like this for column in range n plus one for row in range n plus one.
When we will do this we will be going in this manner because initially the column will remain the same,
but rows will change and majorly every logic will be the same.
Okay.
In many iterations or in many solutions, you will see one thing also getting done.
So I will tell you what exactly this is.
Pay attention.
So first we set the base case okay.
First we set the base case.
After that okay.
As I told we can fill in the boundary by using loop.
Okay.
So many places you will see this also written.
I just want to make sure that you understand that as well.
So we will say that hey for row in range.
row is in range M plus one.
Right.
Let me fill in this particular row.
Let me fill in for this particular row.
Let me fill all the columns value.
So I can do something like this d p of row and column is zero.
I can just say that whatever the cost is cost of row comma zero okay.
The cost which I have plus d p okay.
So c one what will this particular value depend on the d p of top of it.
Right.
We know this particular thing.
So this will become d p of row minus one and zero.
So I am just filling all the values for zero.
And it should start from one because we have handled the base case.
Again I will be doing this in another.
Another question.
So don't have to get confused.
Just I want to assure make sure that you understand each and every solution.
Because many times students understand from different different places, so they should be aware of
each and every approach.
And I think the approach which we have written is the cleanest one, because it actually is using our
understanding of deep recursion and memoization.
Okay, so normally I like to write everything with conditions in a single loop because that is helpful
in handling each and everything.
If you make a error in filling in the boundary first, that is also going to be a problem.
So it is better if we write this or if we fill this up based on the conditions.
Okay everyone.
So yeah, I think that was the major solution for this.
I'm pretty sure that for people doing it for the first time, you must have gotten 70% of it.
The rest 30%.
Just try to see this once again, and I'm sure that it will be clear we will be doing more questions.
I will be making sure to add more solution videos to deep questions, so don't worry on that.
Once you do at least five seven questions, then you will get hold of how exactly we do.
Deep in two dimensional, it's a little difficult.
It's not easy, but provided we move in steps the way we have discussed each and every approach, it
will become a lot easy.
Now, I have discussed every approach to make sure that you understand different, different implementations.
Okay, if you don't do that, if you just remember one implementation, that is going to be a problem
because many questions, it can happen that you might have to use some other implementation.
Okay everyone.
So with that I'm pretty sure you must have understood this.
Now please make sure that you write the code for this as well at your end.
In the coding exercise given to you, it is again very, very important.
Okay, please do that.
You just refer to my code.
You just see the video and then try to write it yourself and you will get a very good idea.
Keep a pen and paper in front of you.
It is very very important to understand.
How exactly are you writing this code?
Okay everyone.
So we will be now doing more questions as of now, please make sure that the coding exercise which is
given to you, you try them out once and we will be shortly updating the solutions to that.