All right.
Now that we know how the recursive tree looks like, writing the code for this would be pretty straightforward.
Let's go ahead and write the pseudocode for this approach.
So we are going to have a helper function which in this case we have just called find cost.
And to this function we'll have to pass two input parameters which is the start index and end index
to identify the range of indices that we are considering in the array, which is given to us to form
the applicable matrices.
So to find cost, I will be passing I and j and I'll have the body of the function.
And when you first call the function after we have written this right.
So when we first call the function, we have discussed that we have to pass the start index as one and
the last index of the array, which is given to us as the end index.
So over here I have one and n minus one.
And again the reason why this is one and not zero is because to form the first matrix I'll need the
first two values in the array.
Now to write the body of the find cost function, we'll have to consider the base case as well as the
recursive case.
Now the base case will be.
If I is equal to j then we can just return zero okay.
Now why is this the case?
It's the case because when I is equal to J we are just dealing with one matrix.
And to reduce one matrix to one matrix there are no multiplications involved.
Right.
So that's why we are returning zero which implies zero multiplications.
Now you can see an example over here.
When we had find cost one comma one, we were just considering this matrix over here.
And we were able to return zero in a similar manner.
Find cost.
Let's say three comma three would just mean this one matrix over here which has the dimensions 30 into
five.
All right.
So we're done writing the base case.
Now let's go ahead and write the recursive case.
Now when we see that I is not equal to J then we would use another variable which we typically call
k.
And k will take the values from I to j minus one.
And for each value of k we will find the cost, or we'll find the number of multiplications involved.
When we partition the array in a way such that k takes the value at hand.
For example, when k takes I, we're doing one particular partitioning.
When k takes the value I plus one, we are taking another way of partitioning array and it goes on in
that manner.
So k will take the values from I to j minus one.
And then we'll find the cost involved for all the values k can take.
And then the minimum between these would be the value that we ascribe to cost.
Okay.
Now let's make some space over here.
We have already discussed over here how to find the cost for a particular value of k.
Okay.
So when k for example in this case k was equal to one, we had to find the cost from I up to k and from
k plus one up to j.
And then the cost of multiplying these two matrices.
So in a general manner we can say that the cost for a particular value of k would be find cost I comma
k plus fine cost k plus one comma j plus the cost of multiplying these two matrices.
Once they are reduced to just one matrix on each side.
Now, these two things, these two aspects are pretty straightforward because we have done this many
times, but this aspect is sometimes a little bit confusing to students.
And for that reason, let's take a closer look at that for this.
First, let's take an example.
Let's say we are trying to multiply two matrices.
And let's say the dimensions involved are one into two and two into three.
Now we have already seen that the cost of multiplying these two arrays is one into two into three.
Now we have discussed that in a previous video.
Notice that in this example over here, the matrices involved when this is the array which is given
to us are 20 into ten, which is what is represented by this side into ten into 40 which is represented
by this side.
So we are trying to actually multiply two matrices which have the dimension 20 into ten and ten into
40.
In this example over here.
And this was pretty straightforward.
We are just considering this single matrix.
But this was formed by multiplying these three matrices.
And when we multiply these three matrices which had the dimension ten into 30 and 30 into five and five
into 40, notice that the final matrix will have the dimensions ten into 40.
Now let's use this to generalize it and try to clearly understand what the cost is for multiplying the
two matrices at the two sides at hand.
So we have seen that this side over here will be a matrix of dimensions array at I minus one into array
at k.
Similarly this side over here, which in the example over here reduces to.
This matrix will have the dimensions array at k into array at j.
Because notice k plus one is equal to two in this example.
And over here we have ten.
And that's index one which is one less than k plus one okay which is just k.
So that's why this dimension is array at k.
And this dimension is the value at the last index which is array at four.
Or in a generalized manner I can say array at j.
So what you discussed so far is this side over here reduces to array at I minus one into array at k.
And this side over here reduces to array at k into array at j.
And when we are trying to multiply these two matrices we know that the cost involved is array at I minus
one into array at k into array j.
And that's what we have seen over here as well.
Right.
And we have discussed this in a previous video also.
So when we multiply two matrices which have these dimensions the cost involved is array at I minus one
into array at k into array at j.
So that's this aspect in this equation.
So we have discussed in detail the recursive approach for solving this question.
And we have also come up with the pseudocode for solving this.
In the next video let's discuss the space and time complexity for the recursive approach for solving
the matrix chain multiplication.