1
00:00:00,080 --> 00:00:00,950
Welcome back.

2
00:00:00,950 --> 00:00:07,550
Let's now implement the recursive solution for solving the matrix multiplication question okay.

3
00:00:07,550 --> 00:00:10,040
So we will be needing a helper function.

4
00:00:10,040 --> 00:00:12,860
And let's just call it find cost okay.

5
00:00:13,820 --> 00:00:18,350
And to this function we will be passing two indices I and j.

6
00:00:18,350 --> 00:00:19,700
Let me just call them I and j.

7
00:00:19,910 --> 00:00:26,720
And what this function will give back is that it will consider all the matrices that we can form when

8
00:00:26,720 --> 00:00:29,210
we pass in these input parameters.

9
00:00:29,210 --> 00:00:32,720
Like for example, let me just quickly take an arbitrary example.

10
00:00:32,720 --> 00:00:36,080
Let us say the array which is given to us is one, two, three, four.

11
00:00:36,080 --> 00:00:44,450
Now if I and j are one and three respectively, then we would be getting back the cost of multiplying

12
00:00:44,450 --> 00:00:49,160
this matrix, which is one into two, and then two into three and three into four.

13
00:00:49,160 --> 00:00:51,800
And let us write the details of this function later.

14
00:00:51,800 --> 00:00:58,430
But ultimately we would just return what we get back from this function when we call it with the input

15
00:00:58,430 --> 00:01:01,160
parameters one and n minus one.

16
00:01:01,280 --> 00:01:03,410
And again notice n is given to us okay.

17
00:01:03,410 --> 00:01:06,620
So n is the size of this array over here okay.

18
00:01:06,620 --> 00:01:10,040
And again we have discussed in detail why we are passing one over here.

19
00:01:10,040 --> 00:01:15,200
And the reason for that is that we need two elements in the array to form a matrix.

20
00:01:15,200 --> 00:01:20,120
Like for example, again if this is the case where the input array is one two, three, four.

21
00:01:20,120 --> 00:01:24,650
Now notice that we need one and two to form a matrix, right.

22
00:01:24,650 --> 00:01:26,540
And two would be index one.

23
00:01:26,540 --> 00:01:29,900
So if we pass zero over here that's this element.

24
00:01:29,900 --> 00:01:31,190
But there is nothing before it.

25
00:01:31,190 --> 00:01:33,170
And we wouldn't be able to form a matrix.

26
00:01:33,170 --> 00:01:34,880
So that's why we are passing one over here.

27
00:01:34,880 --> 00:01:38,060
And again we have discussed this in detail in the previous video.

28
00:01:38,060 --> 00:01:41,720
So this is the skeleton of the approach that we are going to implement.

29
00:01:41,720 --> 00:01:44,240
Now let's go ahead and write the details.

30
00:01:44,240 --> 00:01:50,450
So over here in this helper function we will be writing the base case as well as the recursive case

31
00:01:51,200 --> 00:01:51,710
okay.

32
00:01:51,710 --> 00:01:58,430
And the base case would be the scenario where I is equal to j okay.

33
00:01:58,430 --> 00:02:05,180
And if I is equal to j which is dealing with one matrix and hence no multiplication is needed.

34
00:02:05,180 --> 00:02:08,930
And that's why over here we can just return zero okay.

35
00:02:09,380 --> 00:02:09,920
All right.

36
00:02:09,950 --> 00:02:14,960
Now as part of the recursive case, what we are going to do is we're going to explore every possible

37
00:02:14,960 --> 00:02:16,970
partition using a variable k.

38
00:02:16,970 --> 00:02:23,540
And using that we would be splitting the range from I to j to I to k and k plus one to j okay.

39
00:02:23,540 --> 00:02:29,270
And our aim is to identify the partition in which the multiplication cost would be the least.

40
00:02:29,270 --> 00:02:30,740
So let's get started with that.

41
00:02:30,740 --> 00:02:32,420
And we'll have a for loop over here.

42
00:02:32,420 --> 00:02:40,880
So I can say for let k is equal to I and k will take the values up to j minus one okay and k plus plus.

43
00:02:40,880 --> 00:02:45,740
And we are then going to find the current cost at every particular partition.

44
00:02:45,740 --> 00:02:47,690
So let's just call it cost.

45
00:02:48,530 --> 00:02:50,870
And I'll just have a placeholder for now.

46
00:02:50,870 --> 00:02:57,170
And then after we find this particular cost, what we will do is we'll say cost is the minimum between

47
00:02:57,170 --> 00:02:59,420
this car cost and cost over here.

48
00:02:59,420 --> 00:03:03,680
And again, for that over here initially we would have to define cost okay.

49
00:03:03,680 --> 00:03:07,100
So we will say let cost equal to infinity.

50
00:03:08,250 --> 00:03:13,770
Which is the largest possible value we can give to it, and then we can just say cost is equal to math

51
00:03:13,770 --> 00:03:21,000
dot min, and it's going to be the minimum between the existing value in cost and the cur cost that

52
00:03:21,000 --> 00:03:23,520
we are calculating for this particular partition.

53
00:03:23,550 --> 00:03:23,910
Okay.

54
00:03:23,910 --> 00:03:30,810
So in this way we will be able to identify the least cost or the partition for which the cost of multiplication

55
00:03:30,810 --> 00:03:31,620
is the least.

56
00:03:31,620 --> 00:03:33,510
And then we would just return that.

57
00:03:33,870 --> 00:03:34,290
Okay.

58
00:03:34,290 --> 00:03:37,050
So let's now go ahead and find cur cost.

59
00:03:37,050 --> 00:03:41,220
And as we have discussed in the previous video, there would be three components to it.

60
00:03:41,220 --> 00:03:41,520
Right.

61
00:03:41,520 --> 00:03:48,750
So we would first have to identify the cost of multiplying the matrices that span the range I to k okay.

62
00:03:48,750 --> 00:03:55,260
And then to that we'll have to add the cost of multiplying the matrices that span the range k plus one

63
00:03:55,260 --> 00:03:55,830
to j.

64
00:03:56,040 --> 00:04:01,290
And then finally we would also have to add the cost for multiplying these two matrices.

65
00:04:01,290 --> 00:04:01,680
Okay.

66
00:04:01,680 --> 00:04:07,470
Now to find this and this we would just recursively call the find cost function.

67
00:04:07,470 --> 00:04:08,730
So let's just call this.

68
00:04:08,730 --> 00:04:11,370
So I can say find cost I comma k over here.

69
00:04:11,370 --> 00:04:15,540
And similarly I'll have find cost k plus one j over here.

70
00:04:15,540 --> 00:04:21,600
And then this matrix over here, as we have discussed in the previous video, would finally be a matrix

71
00:04:21,600 --> 00:04:25,890
of the dimension r at I minus one into r at k.

72
00:04:25,890 --> 00:04:28,680
Similarly, this part over here would give us.

73
00:04:28,680 --> 00:04:33,180
Finally a matrix which has the dimensions are at k into RJ.

74
00:04:33,210 --> 00:04:33,570
Okay.

75
00:04:33,570 --> 00:04:39,270
And when we multiply these two matrices, as we have discussed in detail before, the cost for multiplying

76
00:04:39,270 --> 00:04:49,200
that would be r at I minus one into r at k into r at j okay.

77
00:04:49,200 --> 00:04:53,460
And again that's because this is the first dimension for this matrix over here.

78
00:04:53,460 --> 00:04:58,140
And this is the last dimension for this matrix over here okay.

79
00:04:58,140 --> 00:05:02,250
And then the common dimension between these two matrices is r at k.

80
00:05:02,370 --> 00:05:03,060
All right.

81
00:05:03,060 --> 00:05:03,810
So that's it.

82
00:05:03,810 --> 00:05:05,730
So this should help us solve this question.

83
00:05:05,730 --> 00:05:09,870
Now let's go ahead and run this code and see if it's passing all the test cases.

84
00:05:10,870 --> 00:05:12,550
And you can see that it's working.

85
00:05:12,550 --> 00:05:14,230
It's passing all the test cases.

86
00:05:14,230 --> 00:05:19,180
So this is the recursive approach for solving the matrix chain multiplication question.