Welcome back.
Now this is the recursive approach that we have previously implemented.
Now let's go ahead and memoize this.
So first of all let's create a DP array which is going to be a 2D array which has the size n into n.
So let's go ahead and create that and let me call it DP itself okay.
So we'll have array dot from and over here we'll have length n okay.
And we also need n columns.
And let's fill every cell in this DP table with the value minus one.
All right.
Now let's go ahead and modify the helper function slightly.
So over here after the base case before we go ahead and do these computations over here let's first
check whether we had previously computed this or not okay.
So I can say if DP at ij is not equal to minus one.
So if that is the case then we will just return dp at ij and we would not be recomputing this.
Okay.
And again, the reason for this is that notice initially we had filled every cell with the value minus
one.
So if we see that DP at ij is not equal to minus one, it would mean that we previously computed and
stored it.
And that's why it's not equal to minus one.
But if that is not the case then we proceed with these computations over here.
But before we return cost we are going to store it.
So I can say dp at I j is equal to cost.
And then we will just return dp at I j.
Okay.
And you could also return cost.
But let me just write dp at I j over here.
And both are one and the same at this point.
And that's it.
So by just adding a few lines of code we were able to memorize the recursive solution.
Now let's go ahead and run this and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the memoization approach for solving the matrix chain multiplication question.