Welcome back.
Let's now implement the recursive solution for solving the matrix multiplication question okay.
So we will be needing a helper function.
And let's just call it find cost okay.
And to this function we will be passing two indices I and j.
Let me just call them I and j.
And what this function will give back is that it will consider all the matrices that we can form when
we pass in these input parameters.
Like for example, let me just quickly take an arbitrary example.
Let us say the array which is given to us is one, two, three, four.
Now if I and j are one and three respectively, then we would be getting back the cost of multiplying
this matrix, which is one into two, and then two into three and three into four.
And let us write the details of this function later.
But ultimately we would just return what we get back from this function when we call it with the input
parameters one and n minus one.
And again notice n is given to us okay.
So n is the size of this array over here okay.
And again we have discussed in detail why we are passing one over here.
And the reason for that is that we need two elements in the array to form a matrix.
Like for example, again if this is the case where the input array is one two, three, four.
Now notice that we need one and two to form a matrix, right.
And two would be index one.
So if we pass zero over here that's this element.
But there is nothing before it.
And we wouldn't be able to form a matrix.
So that's why we are passing one over here.
And again we have discussed this in detail in the previous video.
So this is the skeleton of the approach that we are going to implement.
Now let's go ahead and write the details.
So over here in this helper function we will be writing the base case as well as the recursive case
okay.
And the base case would be the scenario where I is equal to j okay.
And if I is equal to j which is dealing with one matrix and hence no multiplication is needed.
And that's why over here we can just return zero okay.
All right.
Now as part of the recursive case, what we are going to do is we're going to explore every possible
partition using a variable k.
And using that we would be splitting the range from I to j to I to k and k plus one to j okay.
And our aim is to identify the partition in which the multiplication cost would be the least.
So let's get started with that.
And we'll have a for loop over here.
So I can say for let k is equal to I and k will take the values up to j minus one okay and k plus plus.
And we are then going to find the current cost at every particular partition.
So let's just call it cost.
And I'll just have a placeholder for now.
And then after we find this particular cost, what we will do is we'll say cost is the minimum between
this car cost and cost over here.
And again, for that over here initially we would have to define cost okay.
So we will say let cost equal to infinity.
Which is the largest possible value we can give to it, and then we can just say cost is equal to math
dot min, and it's going to be the minimum between the existing value in cost and the cur cost that
we are calculating for this particular partition.
Okay.
So in this way we will be able to identify the least cost or the partition for which the cost of multiplication
is the least.
And then we would just return that.
Okay.
So let's now go ahead and find cur cost.
And as we have discussed in the previous video, there would be three components to it.
Right.
So we would first have to identify the cost of multiplying the matrices that span the range I to k okay.
And then to that we'll have to add the cost of multiplying the matrices that span the range k plus one
to j.
And then finally we would also have to add the cost for multiplying these two matrices.
Okay.
Now to find this and this we would just recursively call the find cost function.
So let's just call this.
So I can say find cost I comma k over here.
And similarly I'll have find cost k plus one j over here.
And then this matrix over here, as we have discussed in the previous video, would finally be a matrix
of the dimension r at I minus one into r at k.
Similarly, this part over here would give us.
Finally a matrix which has the dimensions are at k into RJ.
Okay.
And when we multiply these two matrices, as we have discussed in detail before, the cost for multiplying
that would be r at I minus one into r at k into r at j okay.
And again that's because this is the first dimension for this matrix over here.
And this is the last dimension for this matrix over here okay.
And then the common dimension between these two matrices is r at k.
All right.
So that's it.
So this should help us solve this question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the recursive approach for solving the matrix chain multiplication question.