1
00:00:00,110 --> 00:00:01,100
Welcome back.

2
00:00:01,100 --> 00:00:07,040
Let's now implement the tabulation approach that we have discussed in the previous video for solving

3
00:00:07,040 --> 00:00:08,990
the matrix multiplication question.

4
00:00:08,990 --> 00:00:15,200
So initially let me create a DP table over here which will have n rows and n columns.

5
00:00:15,200 --> 00:00:19,370
So I can say const dp is equal to array dot.

6
00:00:19,370 --> 00:00:20,120
From.

7
00:00:20,120 --> 00:00:25,940
Then we have length n and we also need n columns.

8
00:00:28,220 --> 00:00:33,950
And what we will do is we will fill every cell in this deep table over here with the value zero.

9
00:00:34,040 --> 00:00:39,080
Now let's go ahead and iterate through the cells in this deep table in a length wise manner.

10
00:00:39,080 --> 00:00:43,820
And again, remember, as we have discussed in the previous video, we are not interested in the first

11
00:00:43,820 --> 00:00:45,200
row and the first column.

12
00:00:45,200 --> 00:00:45,470
Okay.

13
00:00:45,470 --> 00:00:46,670
So let's get started.

14
00:00:46,670 --> 00:00:54,200
So I can say for let L is equal to one l less than equal to n l plus plus.

15
00:00:54,200 --> 00:01:04,550
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

16
00:01:04,550 --> 00:01:05,150
plus.

17
00:01:05,180 --> 00:01:05,570
Okay.

18
00:01:05,570 --> 00:01:09,770
Now typically when we wrote this we always wrote I is equal to zero over here.

19
00:01:09,770 --> 00:01:12,650
But then we are not interested in the first row.

20
00:01:12,650 --> 00:01:14,990
And that's why we start with I is equal to one.

21
00:01:14,990 --> 00:01:23,120
And for each combination of I and L, j is going to equal I plus l minus one.

22
00:01:23,510 --> 00:01:23,900
Okay.

23
00:01:23,900 --> 00:01:25,310
So this is pretty similar.

24
00:01:25,310 --> 00:01:27,860
And the only difference is that we have I is equal to one.

25
00:01:27,860 --> 00:01:29,750
And we have discussed the reason for this.

26
00:01:29,750 --> 00:01:33,140
Now we are going to check whether I is equal to J.

27
00:01:33,740 --> 00:01:40,010
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

28
00:01:40,010 --> 00:01:41,810
dealing with just one matrix.

29
00:01:41,810 --> 00:01:46,340
And if we are just dealing with one matrix, we don't need to do any multiplications.

30
00:01:46,370 --> 00:01:46,910
Okay.

31
00:01:47,000 --> 00:01:55,100
Now if this is not the case then initially we will set dp at I j to equal infinity okay.

32
00:01:55,100 --> 00:01:56,960
Which is the largest possible value.

33
00:01:56,960 --> 00:02:01,940
And then we will go through all the possible partitions to identify the partition.

34
00:02:01,940 --> 00:02:08,360
That gives us the minimum cost for multiplying the matrices that are there between I and J.

35
00:02:08,360 --> 00:02:08,750
Okay.

36
00:02:08,750 --> 00:02:15,470
So over here I will say for let k is equal to I k less than j k plus plus.

37
00:02:15,470 --> 00:02:20,210
And again notice this is the same thing that we have done many times for partition questions.

38
00:02:20,210 --> 00:02:20,660
Okay.

39
00:02:20,660 --> 00:02:30,860
And DP at I, j would be set to the minimum between the value that is currently at DP at ij and the

40
00:02:30,860 --> 00:02:33,620
cost involved for a particular partition.

41
00:02:33,620 --> 00:02:40,310
Okay, the cost for multiplying the matrices for a particular partition and that cost would be dp at

42
00:02:40,310 --> 00:02:52,700
I k plus dp at k plus one j plus the cost of multiplying these two matrices, which would be r at I

43
00:02:52,700 --> 00:02:59,900
minus one into r at k into r at j okay.

44
00:02:59,900 --> 00:03:00,590
And that's it.

45
00:03:00,590 --> 00:03:05,600
Now again notice this is pretty similar to the recursive approach that we have discussed previously.

46
00:03:05,600 --> 00:03:11,360
Now instead of dp at ik and DP at k plus one j, we had recursive calls over there.

47
00:03:11,360 --> 00:03:13,400
And this part over here is the same.

48
00:03:13,400 --> 00:03:13,760
Okay.

49
00:03:13,760 --> 00:03:19,670
That's why it's so beneficial to first write the recursive approach before we go ahead and implement

50
00:03:19,670 --> 00:03:21,020
the tabulation approach.

51
00:03:21,020 --> 00:03:21,860
So that's it.

52
00:03:21,860 --> 00:03:29,150
Now once we are out of this for loop we will just have to return DP at one n minus one.

53
00:03:30,020 --> 00:03:32,810
Because that would give us the solution to the original problem.

54
00:03:32,810 --> 00:03:36,290
Now again, notice the similarity of this to the recursive solution.

55
00:03:36,290 --> 00:03:42,290
In the recursive solution, when we first called the helper function, we did pass the parameters one

56
00:03:42,290 --> 00:03:43,280
and n minus one.

57
00:03:43,280 --> 00:03:45,170
And that's what we have over here as well.

58
00:03:45,170 --> 00:03:45,620
Okay.

59
00:03:45,620 --> 00:03:48,830
And again we have discussed in detail why we have the answer over here.

60
00:03:48,830 --> 00:03:53,990
So let's now go ahead and run this code and see if it's passing all the test cases.

61
00:03:55,190 --> 00:03:58,640
And you can see that it's passing all the test cases.

62
00:03:58,640 --> 00:04:03,020
So this is the tabulation approach for solving the matrix multiplication question.