1
00:00:00,050 --> 00:00:00,920
Welcome back.

2
00:00:00,920 --> 00:00:06,920
In the previous videos we have discussed the recursive as well as the memoization approach for solving

3
00:00:06,920 --> 00:00:07,790
this question.

4
00:00:07,790 --> 00:00:13,580
Let's now discuss the tabulation approach for solving the matrix chain multiplication question.

5
00:00:13,580 --> 00:00:21,590
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

6
00:00:21,590 --> 00:00:22,850
array which is given to us.

7
00:00:22,850 --> 00:00:24,680
So that's what we have over here.

8
00:00:24,680 --> 00:00:29,510
And we will be iterating over these cells over here okay.

9
00:00:29,510 --> 00:00:31,130
Now why is that the case.

10
00:00:31,130 --> 00:00:37,850
We know that this cell over here represents the matrices that start at index one and go up to index

11
00:00:37,850 --> 00:00:38,540
one okay.

12
00:00:38,540 --> 00:00:39,920
Which is this over here.

13
00:00:39,920 --> 00:00:45,170
And we know that this index represents the matrix 20 into ten.

14
00:00:45,290 --> 00:00:48,410
So we don't want the row zero.

15
00:00:48,410 --> 00:00:54,350
Because if you have a cell over here that would imply that you would be able to form a matrix with just

16
00:00:54,350 --> 00:00:56,180
this element over here right now.

17
00:00:56,180 --> 00:00:57,410
Again, let me explain that.

18
00:00:57,410 --> 00:00:58,460
Why is that the case?

19
00:00:58,460 --> 00:01:05,270
Again, we have seen that, for example, this cell over here represents the matrix 20 into ten.

20
00:01:05,270 --> 00:01:05,660
Okay.

21
00:01:05,660 --> 00:01:08,180
So we just had this index over here.

22
00:01:08,330 --> 00:01:14,330
And when we take this index over here it means that we are forming a matrix that's ending over here.

23
00:01:15,480 --> 00:01:18,720
Or this is the number of columns of the matrix.

24
00:01:18,750 --> 00:01:25,950
Now, if we were to take this cell over here, this would correlate with the matrices that go from index

25
00:01:25,950 --> 00:01:27,630
zero up to index one.

26
00:01:27,630 --> 00:01:34,320
But then we know that we are not able to form a matrix that ends with this index over here because there's

27
00:01:34,320 --> 00:01:35,310
nothing before it.

28
00:01:35,310 --> 00:01:35,820
Okay.

29
00:01:35,820 --> 00:01:38,490
And for that reason we don't need this row.

30
00:01:38,490 --> 00:01:43,710
And we also don't need this column over here because again we can't go back right now.

31
00:01:43,710 --> 00:01:49,110
For example, this would mean the indices that start at index four and go up to index zero, which does

32
00:01:49,110 --> 00:01:49,770
not make sense.

33
00:01:49,770 --> 00:01:50,040
Right.

34
00:01:50,040 --> 00:01:53,370
So we don't need this column and we don't need this row.

35
00:01:53,370 --> 00:01:56,280
And in fact we just need these cells over here.

36
00:01:56,280 --> 00:02:03,270
And the reason why these cells are not required is the same reason as to why we have avoided these cells

37
00:02:03,270 --> 00:02:07,560
in previous questions as well, when we implemented length wise iteration.

38
00:02:07,560 --> 00:02:07,980
Okay.

39
00:02:07,980 --> 00:02:14,010
So that's why we're just going to focus on these cells over here in the DP table.

40
00:02:14,010 --> 00:02:14,790
All right.

41
00:02:14,790 --> 00:02:17,670
Now let's see how this spans out.

42
00:02:17,670 --> 00:02:25,830
Now if we see a particular cell where the value of I is equal to J, then we'll just fill zero in that

43
00:02:25,830 --> 00:02:27,210
particular cell okay.

44
00:02:27,210 --> 00:02:31,290
Now again I represents the row value and j represents the column value.

45
00:02:31,290 --> 00:02:37,320
Now if rho is equal to column then we'll just fill zero in these cells because we're just dealing with

46
00:02:37,320 --> 00:02:38,160
one matrix.

47
00:02:38,160 --> 00:02:42,330
And if you're just dealing with one matrix there are no multiplications involved.

48
00:02:42,330 --> 00:02:45,690
Or in other words there are zero multiplications involved.

49
00:02:45,690 --> 00:02:46,380
All right.

50
00:02:46,380 --> 00:02:53,730
Now if that is not the case, to find the value of depee at ij, we'll first allocate the maximum possible

51
00:02:53,730 --> 00:02:55,230
value to dp at ij.

52
00:02:55,380 --> 00:03:02,640
And then we'll use a variable k to iterate through all the possible partitions that we can make, which

53
00:03:02,640 --> 00:03:03,030
is k.

54
00:03:03,030 --> 00:03:06,630
Taking the values from I up to j minus one okay.

55
00:03:06,630 --> 00:03:13,920
And for each value of k, the cost of that particular partition, or the number of multiplications required

56
00:03:13,920 --> 00:03:19,680
to multiply the matrices at hand in a way that we are splitting the matrices involved into two sides

57
00:03:19,680 --> 00:03:29,370
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

58
00:03:29,370 --> 00:03:35,760
formed in these two sides, which is at I minus one into k into array at j.

59
00:03:35,820 --> 00:03:36,270
Okay.

60
00:03:36,270 --> 00:03:42,330
Now notice that this is pretty similar to what we used in the recursive approach as well.

61
00:03:42,330 --> 00:03:44,700
Okay, now let me make some space over here.

62
00:03:44,940 --> 00:03:52,530
Now first of all, this part is the exact same thing that we had in the recursive solution for multiplying

63
00:03:52,530 --> 00:03:55,140
the matrices formed on the two sides.

64
00:03:55,170 --> 00:03:55,560
Okay.

65
00:03:55,560 --> 00:03:59,100
So we're not going to repeat that over here, but in one line.

66
00:03:59,100 --> 00:04:02,880
The reason for this is that the matrices formed on the two sides.

67
00:04:02,880 --> 00:04:09,210
Once we do a partition will have the dimensions array at I minus one into array at k.

68
00:04:11,090 --> 00:04:12,920
And array at K.

69
00:04:15,140 --> 00:04:16,460
Into Aria, J.

70
00:04:18,590 --> 00:04:20,660
And we are multiplying these two matrices.

71
00:04:20,660 --> 00:04:23,780
And that's why the cost involved is this over here.

72
00:04:23,780 --> 00:04:27,020
Now when it comes to these two parts okay.

73
00:04:27,020 --> 00:04:30,350
So when we are making a partition we have two sides.

74
00:04:30,350 --> 00:04:38,330
And this over here will give us the minimum number of multiplications required to multiply the matrices

75
00:04:38,330 --> 00:04:42,830
that can be formed spanning index I to k in the input array.

76
00:04:42,830 --> 00:04:49,310
And this over here will give us the minimum number of multiplications required to multiply the matrices

77
00:04:49,310 --> 00:04:53,690
that can be formed spanning k plus one to j in the input array.

78
00:04:53,690 --> 00:04:54,020
Okay.

79
00:04:54,020 --> 00:04:58,790
So again this is the same logic that we used for the recursive approach as well.

80
00:04:58,790 --> 00:05:06,500
And this underlines why it's so important to first write the recursive solution before attempting to

81
00:05:06,500 --> 00:05:08,090
write the tabulation approach.