Welcome back.
Let's now get started with the recursive approach for solving this question.
Now to discuss this, let's take an example.
Let's say the array which is given to us is this array over here.
And as you can see we have five elements in the array.
And the indices would go from zero up to four.
Now let's say we write a function and let's call that function find cost.
Now when we call this function for the first time, we will be passing the indices one and four.
Because notice the first matrix has the dimensions 20 into ten.
So it's ending at ten.
So that's why we have one over here.
And the last matrix has the dimensions five into 40.
So it's ending at index four.
And that's why we have four over here.
Now this is an important thing that you need to remember okay.
So again the logic is pretty straightforward.
To form the first matrix we need two elements.
So that's why we don't have zero over here.
But we will have one when we call the find cost function for the first time okay.
So these are the two parameters that we will be passing to this function when we call it for the first
time.
And it implies to find the minimum cost for multiplying the matrices that span from index one up to
index four, which in this case are all the matrices involved, which is this, this, this and this.
Okay, so that's four matrices.
All right.
So let's say we have this function.
Now again just to visualize the recursive tree.
Let's see what happens.
So when we call this function and we see that we need to multiply the matrices that span from index
one up to index four, we'll have another variable.
Let's say we use the variable k because that's the typical variable that we use for these partition
problems.
Now you can use any other variable.
Now k will take the values from one up to three okay.
Or from I up to j minus one in this case.
So that means that k will take the values one, two and three.
And each of these represent ways of partitioning the array which is given to us.
Now k is equal to one would mean that we partition it over here k is equal to two would mean that we
are partitioning it over here, and k is equal to three would mean that we are partitioning it over
here.
More of that soon.
Now what will happen is for each of these branches we'll find the number of multiplications involved
okay.
And then we'll just have to find the minimum between these three and return that.
So that would be the answer.
Okay.
So that's the high level way that we are going to approach this in a recursive manner.
Now let's just go down this branch over here to see what happens next.
Let's say k is equal to one okay.
So that means we are partitioning it in this manner.
And whenever we are partitioning it notice there are two sides.
So this is side one and this is side two.
And then we'll just have to identify the cost associated with each side and the cost associated with
multiplying the two matrices that will be formed from each side.
Because eventually each side would be just one matrix because for example, notice over here we have
one, two, three matrices.
But then we are going to multiply these matrices and turn them into one matrix.
And over here we have one matrix.
And in this manner ultimately we will just have one matrix on each side.
So there is a cost associated for ensuring that we just have one matrix on each side.
So we'll have to find those respective costs.
And then there is a cost for multiplying these two matrices.
And when k is equal to one we will again recursively call the find cost function to find the number
of multiplications required when we make a partition like this, and to find that, we will have to
add find cost one comma one plus.
Find cost two comma four plus the cost of multiplying these two matrices okay.
So this one over here has the dimensions 20 into ten.
And then once you multiply these three matrices the dimension would be ten into 40 okay.
And again what is this over here.
Find cost one comma one.
That's this part over here or this side right.
Which starts at one and ends at one.
Because k in this case is one and two comma four is this part over here which is k plus one up to j.
Okay.
And again because we've used k over here this is I comma k.
And this is k plus one up to j.
And in this case notice that fine cost one comma one will just return the value zero.
This would be equal to zero because this actually just represents one matrix which has the dimensions
20 into ten.
And there is no cost of multiplication involved.
Okay.
So that's an interesting thing to note over here.
And to find the value of fine cost two comma four, which implies to find the cost or the minimum cost
of the matrices that span from index two up to index four will have to again use another variable like
k, and it will take the values from two up to four minus one, which in this case is equal to three.
So k can take the values two and three.
And in these two scenarios we'll get the cost of multiplying the matrices.
And the minimum of that would be taken just like what we did over here.
So this is the way that we will recursively solve this question.
And I'm just drawing part of the recursive tree because this is an approach that we are already familiar
with.