Welcome back.
In the previous videos we have discussed the recursive as well as the memoization approach for solving
this question.
Let's now discuss the tabulation approach for solving the matrix chain multiplication question.
Now for this we will need a 2D dp array which is of size n into n, where n is the size of the input
array which is given to us.
So that's what we have over here.
And we will be iterating over these cells over here okay.
Now why is that the case.
We know that this cell over here represents the matrices that start at index one and go up to index
one okay.
Which is this over here.
And we know that this index represents the matrix 20 into ten.
So we don't want the row zero.
Because if you have a cell over here that would imply that you would be able to form a matrix with just
this element over here right now.
Again, let me explain that.
Why is that the case?
Again, we have seen that, for example, this cell over here represents the matrix 20 into ten.
Okay.
So we just had this index over here.
And when we take this index over here it means that we are forming a matrix that's ending over here.
Or this is the number of columns of the matrix.
Now, if we were to take this cell over here, this would correlate with the matrices that go from index
zero up to index one.
But then we know that we are not able to form a matrix that ends with this index over here because there's
nothing before it.
Okay.
And for that reason we don't need this row.
And we also don't need this column over here because again we can't go back right now.
For example, this would mean the indices that start at index four and go up to index zero, which does
not make sense.
Right.
So we don't need this column and we don't need this row.
And in fact we just need these cells over here.
And the reason why these cells are not required is the same reason as to why we have avoided these cells
in previous questions as well, when we implemented length wise iteration.
Okay.
So that's why we're just going to focus on these cells over here in the DP table.
All right.
Now let's see how this spans out.
Now if we see a particular cell where the value of I is equal to J, then we'll just fill zero in that
particular cell okay.
Now again I represents the row value and j represents the column value.
Now if rho is equal to column then we'll just fill zero in these cells because we're just dealing with
one matrix.
And if you're just dealing with one matrix there are no multiplications involved.
Or in other words there are zero multiplications involved.
All right.
Now if that is not the case, to find the value of depee at ij, we'll first allocate the maximum possible
value to dp at ij.
And then we'll use a variable k to iterate through all the possible partitions that we can make, which
is k.
Taking the values from I up to j minus one okay.
And for each value of k, the cost of that particular partition, or the number of multiplications required
to multiply the matrices at hand in a way that we are splitting the matrices involved into two sides
as per the value of k would be dp at I k plus dp at k plus one j plus the cost of multiplying the matrices
formed in these two sides, which is at I minus one into k into array at j.
Okay.
Now notice that this is pretty similar to what we used in the recursive approach as well.
Okay, now let me make some space over here.
Now first of all, this part is the exact same thing that we had in the recursive solution for multiplying
the matrices formed on the two sides.
Okay.
So we're not going to repeat that over here, but in one line.
The reason for this is that the matrices formed on the two sides.
Once we do a partition will have the dimensions array at I minus one into array at k.
And array at K.
Into Aria, J.
And we are multiplying these two matrices.
And that's why the cost involved is this over here.
Now when it comes to these two parts okay.
So when we are making a partition we have two sides.
And this over here will give us the minimum number of multiplications required to multiply the matrices
that can be formed spanning index I to k in the input array.
And this over here will give us the minimum number of multiplications required to multiply the matrices
that can be formed spanning k plus one to j in the input array.
Okay.
So again this is the same logic that we used for the recursive approach as well.
And this underlines why it's so important to first write the recursive solution before attempting to
write the tabulation approach.