1
00:00:00,230 --> 00:00:01,280
Welcome back.

2
00:00:01,280 --> 00:00:05,210
Now this is the recursive approach that we have previously implemented.

3
00:00:05,210 --> 00:00:07,280
Now let's go ahead and memoize this.

4
00:00:07,280 --> 00:00:13,910
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.

5
00:00:13,910 --> 00:00:18,320
So let's go ahead and create that and let me call it DP itself okay.

6
00:00:18,320 --> 00:00:23,360
So we'll have array dot from and over here we'll have length n okay.

7
00:00:23,360 --> 00:00:26,030
And we also need n columns.

8
00:00:27,710 --> 00:00:32,300
And let's fill every cell in this DP table with the value minus one.

9
00:00:32,300 --> 00:00:32,870
All right.

10
00:00:32,900 --> 00:00:36,350
Now let's go ahead and modify the helper function slightly.

11
00:00:36,350 --> 00:00:42,800
So over here after the base case before we go ahead and do these computations over here let's first

12
00:00:42,800 --> 00:00:46,460
check whether we had previously computed this or not okay.

13
00:00:46,460 --> 00:00:54,080
So I can say if DP at ij is not equal to minus one.

14
00:00:54,080 --> 00:01:00,560
So if that is the case then we will just return dp at ij and we would not be recomputing this.

15
00:01:01,560 --> 00:01:02,220
Okay.

16
00:01:02,220 --> 00:01:07,260
And again, the reason for this is that notice initially we had filled every cell with the value minus

17
00:01:07,260 --> 00:01:07,560
one.

18
00:01:07,560 --> 00:01:14,130
So if we see that DP at ij is not equal to minus one, it would mean that we previously computed and

19
00:01:14,130 --> 00:01:14,760
stored it.

20
00:01:14,760 --> 00:01:17,190
And that's why it's not equal to minus one.

21
00:01:17,190 --> 00:01:21,480
But if that is not the case then we proceed with these computations over here.

22
00:01:21,480 --> 00:01:24,720
But before we return cost we are going to store it.

23
00:01:24,720 --> 00:01:29,340
So I can say dp at I j is equal to cost.

24
00:01:29,490 --> 00:01:32,100
And then we will just return dp at I j.

25
00:01:32,100 --> 00:01:32,580
Okay.

26
00:01:32,580 --> 00:01:34,410
And you could also return cost.

27
00:01:34,410 --> 00:01:36,630
But let me just write dp at I j over here.

28
00:01:36,630 --> 00:01:38,640
And both are one and the same at this point.

29
00:01:38,640 --> 00:01:39,420
And that's it.

30
00:01:39,420 --> 00:01:45,000
So by just adding a few lines of code we were able to memorize the recursive solution.

31
00:01:45,000 --> 00:01:48,840
Now let's go ahead and run this and see if it's passing all the test cases.

32
00:01:49,860 --> 00:01:51,510
And you can see that it's working.

33
00:01:51,510 --> 00:01:53,250
It's passing all the test cases.

34
00:01:53,250 --> 00:01:58,830
So this is the memoization approach for solving the matrix chain multiplication question.