Welcome back.
Now to build the Intuition.
Let's make a few interesting observations.
Let's say the array which is given to us is this array over here okay.
Now there are various ways in which we could partition this array.
One way would be if we had a line drawn over here, we would be partitioning this array into two parts.
Okay.
So the first part over here represents the matrix 20 into ten okay.
And the second part over here would represent the matrix that we finally get when we multiply these
three matrices which have the size ten into 30, 30 into five and five into 40.
So notice that this partitioning over here is equivalent to saying that I'll have the matrix of size
20 into ten over here.
And I'll multiply this matrix with the matrix that I get when I multiply these three matrices.
Okay.
So this is one way of multiplying the matrices at hand.
And let's say in this scenario we just identify the number of multiplications involved.
Now another way in which we could partition the array which is given to us is let's say we could have
a line over here instead of having a line over here.
Okay.
Now having a partition over here would imply that.
Let me first multiply these matrices over here, which have the size 20 into ten and ten into 30.
Okay.
So this over here will give me a matrix.
And I will multiply this matrix over here with the matrix that I will get when I multiply 30 into five
and five into 40.
Okay.
And let's say again, in this scenario, we write the code such that we identify the number of multiplications
involved.
In this way, we are able to identify all the different ways in which we can actually multiply the matrices
which are given to us, and identify the number of multiplications involved in each case.
And then we would just need to identify the best way or the way in which the number of involved multiplications
are the least.
So in this way this question is actually very similar to other partitioning questions okay.
So again this is the intuition that we will use to first come up with the recursive solution.
And then we'll write the memoization solution.
And finally we'll come up with the tabulation approach in the next video.
Let's get started with the recursive approach.