All right.
Welcome back.
So we are done discussing the recursive approach for solving this question.
Now let's take a look at how we can implement the memoization approach.
And for this we'll just need to add a few lines of code to the recursive approach that we have already
implemented.
So let's get started with the memoization approach.
We have already drawn out the recursive tree or part of the recursive tree in previous videos.
And this is how it looked like.
Let's say you had an array which had five elements.
So the indices involved would go from zero up to four.
And over here when we call the find cost function for the first time, we'll pass the index one and
four, which means that we're trying to find the cost of multiplying all the matrices that can be formed
starting at index one and going up to index four.
And then we have already discussed how we take another variable k.
We make all the different possible partitions.
And we find the partition that gives us the minimum cost for multiplying all the matrices involved.
Now first let's discuss how does this become a question where possibly memoization can help?
Or in other words, how do we identify this as a possible candidate for memoization?
When you take a look at the recursive tree, notice you have multiple branches over here.
And we have previously discussed that in these type of scenarios, there is a high likelihood for overlapping
subproblems.
Now to take a more detailed view and to actually see that there are overlapping subproblems, let's
try to draw out the recursive tree or part of the recursive tree.
And let's just consider the indices.
So the indices involved in the array which is given to us start at index zero and goes up to index four.
And we have already seen that the first time we call the find cost function the indices passed are one
comma four.
Now the tree would look like this okay.
So you start with the indices one comma four.
And then the possibilities are that k can take the values 1 to 3.
And when k takes the value one, you partition it in a way that one side goes from 1 to 1 and the other
side goes from 2 to 4.
Okay, now to find the answer to this subproblem, k can take the values two and three.
Or there are these two ways of partitioning this subarray okay.
And again when k is equal to two the parts are two comma two and three comma four.
And when k is equal to three, the different parts of the two sides are two comma three and four comma
four.
Okay.
And again this is just part of the recursive tree.
Now notice that three comma four occurs two times okay.
You have it over here and you have it over here.
Now when you did compute this if we had stored it, then when we encounter this part we could just retrieve
it without actually going ahead and computing it again.
Right.
So again, that's what we imply with overlapping subproblems in a similar way you have four comma four
over here and here.
And you will see that there are multiple overlapping subproblems if you draw out the complete recursive
tree.
And again four comma four is technically something that we will not compute because these two are equal.
But again, I'm just showing it over here to indicate that things are in fact repeating.
So in this question there are overlapping subproblems.
And the second thing is that in this question there is optimal substructure, because we can use the
solution to a subproblem to solve the problem okay.
And again what does that mean.
It means that for example, if we know the answer to two comma four, we can use this to find this answer
where k is equal to one for one comma four okay.
And if we know these we can find the answer to this.
Similarly if we know these we can find the answer to this okay for these three versions.
So it means that we are able to use the solution to subproblems to solve the problem.
And that means that this question has optimal substructure.
Now because this question has both overlapping subproblems and optimal substructure, it's an ideal
candidate for dynamic programming.
And that's why we can solve this question or optimize this question using memoization.
All right.
So getting back to the question, we have already seen how the recursive tree looks like.
And we have already seen how to recursively solve the question.
Now memoization is just about storing stuff and then avoiding recomputing.
Right.
So after we check the base case which is over here, and before we go ahead and compute this part,
which is the recursive case, we will first check whether we have already computed this particular combination
of I and J.
And if we had computed it previously, we would just return it, and if not, we'll go ahead and compute
it.
And this time we would store it so that if we encounter this again in the future, we will not require
to recompute it.
So this is all that memoization is about.
Now let's see how we actually go about doing this.
Now for this, let's say that the array which is given to us is again this array which has five elements.
And for the memoization approach over here, we will need a two dimensional array which will be of size
n into n.
So notice in this case because we have five elements we have five columns and five rows okay.
So the indices of the rows and columns span from zero and go up to four.
And in each cell we would store the cost for multiplying the matrices that can be formed that span from
the particular row index up to the particular column index.
For example, this cell over here will store the cost of multiplying the arrays that can be formed starting
at index two and going up to index four.
And in this example that would be the matrices ten into 30.
30 into five and five into 40.
Okay, so this cell over here will store the minimum number of multiplications required to multiply
these three matrices.
So that's about it.
Now when we take a look at the code you will see that this is just the recursive approach with storing
stuff in this DP table.
That's it.
So it's going to be just a few lines of code a few tweaks here and there.
And we would have converted the recursive approach to the memoization approach.