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

2
00:00:01,130 --> 00:00:03,590
Now to build the Intuition.

3
00:00:03,590 --> 00:00:06,410
Let's make a few interesting observations.

4
00:00:06,410 --> 00:00:10,850
Let's say the array which is given to us is this array over here okay.

5
00:00:10,850 --> 00:00:15,260
Now there are various ways in which we could partition this array.

6
00:00:15,260 --> 00:00:21,890
One way would be if we had a line drawn over here, we would be partitioning this array into two parts.

7
00:00:21,890 --> 00:00:22,370
Okay.

8
00:00:22,370 --> 00:00:29,090
So the first part over here represents the matrix 20 into ten okay.

9
00:00:29,180 --> 00:00:37,310
And the second part over here would represent the matrix that we finally get when we multiply these

10
00:00:37,310 --> 00:00:44,600
three matrices which have the size ten into 30, 30 into five and five into 40.

11
00:00:44,600 --> 00:00:52,430
So notice that this partitioning over here is equivalent to saying that I'll have the matrix of size

12
00:00:52,430 --> 00:00:54,290
20 into ten over here.

13
00:00:54,290 --> 00:01:01,730
And I'll multiply this matrix with the matrix that I get when I multiply these three matrices.

14
00:01:01,730 --> 00:01:02,270
Okay.

15
00:01:02,270 --> 00:01:06,650
So this is one way of multiplying the matrices at hand.

16
00:01:06,650 --> 00:01:12,830
And let's say in this scenario we just identify the number of multiplications involved.

17
00:01:12,830 --> 00:01:18,650
Now another way in which we could partition the array which is given to us is let's say we could have

18
00:01:18,650 --> 00:01:21,050
a line over here instead of having a line over here.

19
00:01:21,050 --> 00:01:21,560
Okay.

20
00:01:21,560 --> 00:01:25,490
Now having a partition over here would imply that.

21
00:01:25,490 --> 00:01:33,860
Let me first multiply these matrices over here, which have the size 20 into ten and ten into 30.

22
00:01:34,100 --> 00:01:34,520
Okay.

23
00:01:34,520 --> 00:01:37,130
So this over here will give me a matrix.

24
00:01:37,130 --> 00:01:45,590
And I will multiply this matrix over here with the matrix that I will get when I multiply 30 into five

25
00:01:47,240 --> 00:01:48,830
and five into 40.

26
00:01:51,790 --> 00:01:52,420
Okay.

27
00:01:52,420 --> 00:01:58,780
And let's say again, in this scenario, we write the code such that we identify the number of multiplications

28
00:01:58,780 --> 00:01:59,440
involved.

29
00:01:59,440 --> 00:02:06,370
In this way, we are able to identify all the different ways in which we can actually multiply the matrices

30
00:02:06,370 --> 00:02:11,590
which are given to us, and identify the number of multiplications involved in each case.

31
00:02:11,590 --> 00:02:18,160
And then we would just need to identify the best way or the way in which the number of involved multiplications

32
00:02:18,160 --> 00:02:19,120
are the least.

33
00:02:19,120 --> 00:02:26,470
So in this way this question is actually very similar to other partitioning questions okay.

34
00:02:26,470 --> 00:02:32,200
So again this is the intuition that we will use to first come up with the recursive solution.

35
00:02:32,200 --> 00:02:34,900
And then we'll write the memoization solution.

36
00:02:34,900 --> 00:02:38,890
And finally we'll come up with the tabulation approach in the next video.

37
00:02:38,890 --> 00:02:41,890
Let's get started with the recursive approach.