Welcome back.
Let's now implement the tabulation approach that we have discussed in the previous video for solving
the matrix multiplication question.
So initially let me create a DP table over here which will have n rows and n columns.
So I can say const dp is equal to array dot.
From.
Then we have length n and we also need n columns.
And what we will do is we will fill every cell in this deep table over here with the value zero.
Now let's go ahead and iterate through the cells in this deep table in a length wise manner.
And again, remember, as we have discussed in the previous video, we are not interested in the first
row and the first column.
Okay.
So let's get started.
So I can say for let L is equal to one l less than equal to n l plus plus.
And for each value of l I will say for let I is equal to one I less than or equal to n minus l I plus
plus.
Okay.
Now typically when we wrote this we always wrote I is equal to zero over here.
But then we are not interested in the first row.
And that's why we start with I is equal to one.
And for each combination of I and L, j is going to equal I plus l minus one.
Okay.
So this is pretty similar.
And the only difference is that we have I is equal to one.
And we have discussed the reason for this.
Now we are going to check whether I is equal to J.
And if this is the case then we can just say dp at I, j is equal to zero because in this case we are
dealing with just one matrix.
And if we are just dealing with one matrix, we don't need to do any multiplications.
Okay.
Now if this is not the case then initially we will set dp at I j to equal infinity okay.
Which is the largest possible value.
And then we will go through all the possible partitions to identify the partition.
That gives us the minimum cost for multiplying the matrices that are there between I and J.
Okay.
So over here I will say for let k is equal to I k less than j k plus plus.
And again notice this is the same thing that we have done many times for partition questions.
Okay.
And DP at I, j would be set to the minimum between the value that is currently at DP at ij and the
cost involved for a particular partition.
Okay, the cost for multiplying the matrices for a particular partition and that cost would be dp at
I k plus dp at k plus one j plus the cost of multiplying these two matrices, which would be r at I
minus one into r at k into r at j okay.
And that's it.
Now again notice this is pretty similar to the recursive approach that we have discussed previously.
Now instead of dp at ik and DP at k plus one j, we had recursive calls over there.
And this part over here is the same.
Okay.
That's why it's so beneficial to first write the recursive approach before we go ahead and implement
the tabulation approach.
So that's it.
Now once we are out of this for loop we will just have to return DP at one n minus one.
Because that would give us the solution to the original problem.
Now again, notice the similarity of this to the recursive solution.
In the recursive solution, when we first called the helper function, we did pass the parameters one
and n minus one.
And that's what we have over here as well.
Okay.
And again we have discussed in detail why we have the answer over here.
So let's now go ahead and run this code and see if it's passing all the test cases.
And you can see that it's passing all the test cases.
So this is the tabulation approach for solving the matrix multiplication question.