Hello all and welcome back.
So in this video let us now move forward and try to solve this question using memoization.
We have solved the min cost path question in the last video using recursion.
I am pretty sure that all of you must have tried both the approaches, and the same will be a lot clear
to you.
So now let's move forward and see.
Should we apply memoization here or not?
Okay, so again the basic idea is the same for DP right.
For us to apply DP we have to first see if there are multiple subproblems which we are solving again
and again.
Right.
So if we talk about this particular problem in which we are solving, we normally start from two comma
two okay.
And if we go back to our code we used to make call like this m and n minus one then m minus one and
n and then m minus one n minus one okay.
So effectively that means at each and every position I am making three calls two comma one, one comma
two, and one comma one.
Okay.
So these are the three places.
Or you can say subproblems on which my answer depends.
Now this two comma one.
It's also going to make the same calls.
So it's going to be two comma zero.
Then we will have one comma one and one comma zero right.
Similarly this one by one by two space.
So let me draw it as well here.
So this is the exact position where we are.
Now this depends on these three boxes or these three subproblems.
Right everyone.
Now this two comma one Okay.
So let me write down the indexes.
Two comma one is this box.
If we see this particular will depend on these three problems right.
So the first is two comma zero which is this one.
Then next is one comma one which is this one.
And then we have one comma zero okay.
So pretty sure that you are able to understand each and every one of them.
Now similarly this one comma two this particular box will depend on these three problems okay.
So let us write that down.
We will have first one where we are subtracting the negative.
Then we will have zero comma two and finally subtracting both of them okay.
So great everyone, I hope you are able to see this now when I am standing on this one comma two.
This is one.
Comma two.
In this this is getting dependent on first one comma one which is this one which is left.
Now this is top if you will see zero comma two.
And last is diagonal.
Okay.
In a similar manner let us write for one comma one.
This one comma one will depend on these three boxes.
Okay.
So it will be one comma zero.
Zero comma one.
And finally zero comma zero.
So this overall box depends on one comma zero which is this one.
Then it depends on this one which is zero comma one.
And finally zero comma zero.
Okay great.
So let us see.
Do we have some sub problems here which are overlapping.
I think we have.
So if you will see here this is a same problem one comma one and one comma one okay.
Then similarly we have zero comma one here, zero comma one here.
Okay.
One comma zero is here, one comma zero is here.
Okay.
So I hope you get the idea that there are.
Subproblems.
Which we are solving.
Again and again.
That's a very good case of applying dynamic programming, something which we have discussed in the first
class, that dynamic programming can be applied to cases like this.
Right, everyone?
Now, if we think about this here, we have a 2D space.
Here we are dealing with a particular 2D space or 2D matrix.
Now it will be a lot better if I can make a memoization array or a list which is 2D in nature.
So let us move forward and see how we will be doing that.
Now I will be making a list of 2D space.
Minute.
So we will have something like this.
This will be my memoization space or memoization list.
Right?
Now, one thing to always and always remember in these kind of questions.
Normally we say them as 2D deep because now we have a 2D space to overall handle or see, right.
So in 2D deep okay.
Or rather in deep as well, we have to always make sure that we are clearing out few things.
The first is the space we have made that space or list size okay.
Second, if we see it's actually what each.
Box.
Signifies.
What does this mean?
So let's say these are my indexes zero one, two.
What does this specifically one comma, one box means?
It is very important to specify this thing if or when you are solving a question in DP.
In 1d dp it was pretty straightforward for Fibonacci.
We were saying that for I is equal to let's say five.
It is the fifth Fibonacci number, right?
Now, in a way, if you think we are, we saw in the tree as well.
These are just all the subproblems, right?
Everyone.
So these are just all the subproblems which are of the same nature.
That is why I was able to call recursion here.
Right.
So what does like if we go back to our basics recursion, we learned that it is yes, it is a function
calling itself in terms of application.
But the basic idea was not that basic idea was that if a problem depends on similar smaller problem.
So all I am saying is that hey, I will get you the two comma two minimum cost if you give me the minimum
cost from these overall problems, right?
What does that mean?
What does that transforms to is basically that each and every of these boxes give the answer to our
sub problem.
That is minimum cost path from zero comma zero to this box or vice versa because the cost is going to
be the same.
If you are taking a minimum path from A to B, then that path will there be from B to A?
Okay, great.
So I hope this thing is clear.
Again, it is very, very important.
We have to always make sure to specify that what each and every box or each and every location or space
signifies.
After that, only we can just move forward.
Okay, great.
Now, if I have to find the minimum cost to reach at this position.
Okay.
And I have the minimum cost one, minimum cost two and minimum cost three, then I think I can just
take minimum of C1, C2 and C3 and add whatever cost I have.
So cost m comma n okay.
So I will repeat this understanding again because at least one, two and three box I have the minimum
cost which will be there from zero zero to this particular position, or from this position to zero
comma zero.
I can just take their minimum and add the cost.
Okay.
Where I am standing.
So let me just write it clearly.
Cost m comma n.
Okay everyone.
So pretty sure that this thing is now a lot clearer.
So idea is that I will be making this 2D list.
Okay, we'll be calling that memo a memoization array or list.
Right.
And in each and every box, along with calculating the answer, I will save the same as well.
Okay, if I am saving that, then of course we don't need to calculate or solve our problem again and
again.
And that is just the basic idea okay.
We have seen in deep how that will help us to save the save the time.
Now we can see this thing once a couple of things here.
This time complexity is of the order three to the power N, because we are calling on each and every
from each and every location in three directions, right?
So each and every tree is having three children one, two, three, then one, two, three.
Okay.
Along with that, we can be sure of one more thing.
That is M cross N will be size of our memo list.
The reason is same because I have m cross n spaces or boxes or subproblems which I am solving.
It's just that I'm solving them again and again in recursion.
So that's why it's taking a lot of time.
So I'm pretty sure that everyone now this will be a lot more clear that what exactly is happening here.
Right.
And that is what is very important to understand in 2D DP.
So I will repeat the steps and I will write them down as well, so that we are 100% clear.
Let me add a page and let us see the steps which are there in 2D.
Steps.
For solving.
2D dp using
memoization.
These are all practical based steps.
You can find some big or I would say long list of steps in some website or something.
But I think the things which you learn via practical that are the one which you actually understand,
okay.
And it is not some exam where you have to write them down.
It's majorly for you to remember.
Okay?
So please make sure that you always understand these things by your own experience rather than following
any, I would say, tutorial or some long list of this.
Okay, first
solve problem
Using recursion that will surely be there.
Okay, second exactly what we did create recursion tree.
And see if subproblems.
Are overlapping.
Okay so that's the second part everyone.
Third find out.
Unique subproblems.
Once we have the unique subproblems, we will have an idea that okay how what should be our dimensions
majorly of our memoization array.
Fourth, create the memo space.
Okay.
So it can be a 2D list.
It can be a 1D list.
Like again these are the basic steps which we are following till now.
Fifth which is very important.
Define what each box or individual.
Memory.
In space signify.
This step is very important.
We have to make sure that we are clear on what exactly each and every of this space, individual space
or box in our whole memoization array or list signify.
Okay.
Because based on that, only I will be able to say that, hey, I have this particular thing.
Now, based on this, I can write my logic.
Okay.
Sixth, write down.
Code and save the solution.
Okay, so pretty sure now it will be a lot more clear to everyone what exactly we have to do.
So if this is clear then let us move forward and try to code this down.
I'm pretty sure that it will be a lot more clear when we code it.
Okay, so let me just close this one and let us write.
Min cost path.
Memoization cost m n and a memo space will be passed.
Now we can create a memo space.
Okay.
Memoization is something like this.
So we are creating as of now using this code write for I in range we can say n plus one.
Let's say it's m and n right.
So let us say this.
We want a space here which is equivalent to m cross n okay.
So n is the number of columns and n is the number of rows.
So once I have this space I can just further call my.
Let me just make sure one minute.
Yeah.
Now this space is there I'm using list comprehension here.
Pretty sure all of you must have used that.
So once I have this array 1D array okay 1D list I just want it for.
M times more okay.
So this is the rows and these are the columns.
First I will create a single row.
And then I will just copy that row m times I am taking m plus one for of course a easy overall use.
Okay everyone.
So I hope this is clear.
Now let us now try to write down the code and see how exactly things will happen.
Great.
So first will be the base case.
Okay.
If m zero and n zero we can just say that hey, you are on the starting point.
That is the cost.
Okay.
You can think of this as a single, uh, cost matrix as well.
Okay.
Something like this.
If you are on zero and you want to reach on zero, that's the cost.
Great.
Next is our out of bounds error.
Right?
So out of bounds.
What we used to do here everyone.
If m less than zero and n less than zero.
Not.
And again or we used to return float over infinity.
Okay.
Pretty sure that this must also be clear.
Once this is done, I have to check if I have previously solved my problem.
So for that, we can just write this condition.
If this is not equal to minus one, then I can say that okay, return whatever is here because that
signifies that I have solved my problem.
Great.
After that, I will have to make these recursive calls.
So that is going to be the same.
We have to still make these recursive calls.
Now I cannot store these recursive call in m and n minus one because these are not the answers okay.
These are just the recursive calls for getting the cost.
Once I get my answer, something which we wrote like this.
Okay, so cost of m comma n plus minimum of cost.
Left cost.
Top cost.
Diagonal.
Once I do this and I return the answer, I have to just make sure that I am so saving this answer as
well.
Equals answer.
Okay, so pretty straightforward code.
Uh, just exactly what we did in the last, uh, video using recursion.
Just that this time I have used a memoization array to store my answer.
And because it is in 2D space, we just have to make sure that we do few things.
Okay, great.
So let me run this now everyone.
One minute.
So again we will have to just make sure we call this here and pass the memoization array.
It's normally a good practice to pass this uh memoization space or array.
Right.
Uh, we can of course.
Uh, all of you might be thinking that, yes, we can, uh, declare it globally as well, but normally
it's a very good practice if you are defining it and passing it with each function.
Because if, let's say some changes are happening, okay, we can make sure that it is getting passed
and everything is happening there only.
Okay, great.
So we have to just call this memoization and memo will be there.
Okay.
So what we can do I think it is giving us the answer.
But something which we can do here is we can print our memo array as well.
So if you will see here what exactly this memo array is becoming, let us see this.
So let's say for row in memo let us print this row okay.
Print row.
Okay.
And in print see.
So here it is minus one okay.
Because we are starting from here.
This is the base case.
So it is not getting updated.
Ideally we can even make sure that we do this as well.
We can update this as well.
Now if you will see this is eight here because this is the answer.
If I start from here and go all the way till here, this is what I should get.
What.
This is the minimum cost.
This ten is actually the minimum cost.
If I start from this zero comma zero and go till here.
Okay, so pretty sure that this must be clear to each and every one of you.
Pay attention.
See one plus four, five, six.
And then this is 11.
Okay.
So some other part will be there which we will be following.
But the idea is and I think it is this part.
See 12323 and this.
So something like the path which is getting followed.
We have to see that.
But each and every of these things they are storing the answer which or the minimum path through which
we can reach out to this particular location.
For this particular location, it is one plus 4 or 5.
Then we are taking this diagonal overall.
Okay.
So now we have this saved already.
So of course we will be not making those many calls.
And we have also improved the complexity of our code a lot.
So this is how if we have multiple dependencies we will be solving our question.
Now just one thing I want to make sure that you understand.
So for that again we will do the same thing.
Let me copy this whole code.
And before we move on to the next, uh, approach that is the tabulation approach, let me edit this
code.
I want all of you to see that how exactly this is getting filled, because it is very important to understand
how exactly this memoization is getting filled.
Okay.
If you understand that, then I'm pretty sure you will be able to understand how to write the tabulation
approach as well.
Many students what they do.
They just follow this particular, uh, memorization.
They don't go deep into this.
They just say that, yes, my answer is getting saved, but how exactly is it filling?
That thing is very important.
Okay, so pay attention, everyone.
Uh, okay.
We have some list like these should be fine.
Uh, 123482153.
Uh, memo will also be created something like this only.
So let it create.
This is just range.
Uh, getting folder should be fine.
Okay, so this is the, uh, memoization.
Everyone should be fine.
Let us see.
So these are my list.
You can just think of this as your memoization.
Uh, metrics pay attention.
So very first time our M and n is two.
So let me just draw on top of that as well.
Right now we are starting from this position okay.
This is the position we are starting.
It has dependencies here, here and here.
Pay attention on what exactly are we making the call?
Okay, so see, everyone, let me just remove the drawings.
Just follow this M and N call and you will get an idea.
I want to show you that how exactly this memoization array or list will fill.
Because then you will be clear that okay, which overall node or which overall space has some dependency
okay.
So pay attention.
We will see that where exactly it starts getting filled.
We can just till then make these calls.
So we are making a call to two one then to two zero okay let us now move forward.
This is two comma minus one.
So we will just get infinity here okay.
Then we are making a call to one comma zero.
So one comma zero.
Here it will make a further call.
So calls are going to get made a lot.
This is going to return infinity.
Finally you will see that zero comma zero.
We are making a call.
Okay, now just let me explain you here as well.
If we see this particular thing so that you are able to write the code for your tabulation approach
as well.
So pay attention everyone.
This is again a 2D space okay.
Here we are starting from this particular space I make a call to this to this.
Then we are this is going to make a call from this.
It will get infinity okay.
Then make a call to top.
Then it makes another call.
Here it will get infinity.
Finally we will reach here.
Now here.
Because this is a base case okay.
Again the thing to understand this is a base case is a base case.
We will have the answer here.
We will have some answer here.
We will go back.
And now it will try to make a call in the diagonal, which is infinity.
The point which I want to make you understand is that these corner elements, they do not have any dependencies
rather than just the top element.
I hope this is clear as well.
Right.
So what I am saying is that just this answer, it doesn't have any dependency.
It's a base case.
This particular position, this particular box, it just depends on the top because the left and the
diagonal both are overall not present.
So the answer will be infinity from there.
Same for this okay.
In a very similar way, this particular box just this is something which is present above and diagonally.
We will get infinity okay.
So based on this understanding now you will have to write the tabulation code as well.
Right.
Now many students they face this difficulty because they don't understand that how this memoization
array will fail because I have followed this approach from the start, that if you understand that how
this memoization array will fail, you will be able to understand this properly.
And no code for pure DP will be difficult for you.
And I have shown you here as well that how exactly it is going to fail.
Okay, so once we have everything filled here, then this will make a call to top.
We have this answer.
It will make a call to top.
So like this our whole space will get filled.
And this is very important to understand again so that you can write the memoization approach or sorry
tabulation approach.
That is the pure DP solution.
Okay.
So I hope this idea is clear a little bit in the Python tutor.
It is getting a lot messy.
So I want to make sure that you understand this particular point based on this understanding.
You should be right or you should be comfortable to write your pure DP or tabulation approach.
So please make sure that you try this out once.
And in the next video we will see that how exactly can we solve that okay.