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

2
00:00:01,280 --> 00:00:06,200
Let's now get started with the recursive approach for solving this question.

3
00:00:06,230 --> 00:00:09,050
Now to discuss this, let's take an example.

4
00:00:09,050 --> 00:00:12,680
Let's say the array which is given to us is this array over here.

5
00:00:12,680 --> 00:00:16,250
And as you can see we have five elements in the array.

6
00:00:16,250 --> 00:00:19,430
And the indices would go from zero up to four.

7
00:00:20,090 --> 00:00:25,430
Now let's say we write a function and let's call that function find cost.

8
00:00:25,460 --> 00:00:32,120
Now when we call this function for the first time, we will be passing the indices one and four.

9
00:00:32,120 --> 00:00:38,090
Because notice the first matrix has the dimensions 20 into ten.

10
00:00:38,090 --> 00:00:39,860
So it's ending at ten.

11
00:00:39,860 --> 00:00:41,570
So that's why we have one over here.

12
00:00:41,570 --> 00:00:45,860
And the last matrix has the dimensions five into 40.

13
00:00:45,860 --> 00:00:47,870
So it's ending at index four.

14
00:00:47,870 --> 00:00:49,730
And that's why we have four over here.

15
00:00:49,730 --> 00:00:53,660
Now this is an important thing that you need to remember okay.

16
00:00:53,660 --> 00:00:56,090
So again the logic is pretty straightforward.

17
00:00:56,090 --> 00:00:58,760
To form the first matrix we need two elements.

18
00:00:58,760 --> 00:01:00,800
So that's why we don't have zero over here.

19
00:01:00,800 --> 00:01:05,630
But we will have one when we call the find cost function for the first time okay.

20
00:01:05,630 --> 00:01:11,060
So these are the two parameters that we will be passing to this function when we call it for the first

21
00:01:11,060 --> 00:01:11,390
time.

22
00:01:11,390 --> 00:01:20,060
And it implies to find the minimum cost for multiplying the matrices that span from index one up to

23
00:01:20,060 --> 00:01:27,080
index four, which in this case are all the matrices involved, which is this, this, this and this.

24
00:01:27,080 --> 00:01:29,120
Okay, so that's four matrices.

25
00:01:29,420 --> 00:01:30,170
All right.

26
00:01:30,170 --> 00:01:32,390
So let's say we have this function.

27
00:01:32,390 --> 00:01:35,720
Now again just to visualize the recursive tree.

28
00:01:35,720 --> 00:01:37,130
Let's see what happens.

29
00:01:37,130 --> 00:01:43,760
So when we call this function and we see that we need to multiply the matrices that span from index

30
00:01:43,760 --> 00:01:47,270
one up to index four, we'll have another variable.

31
00:01:47,270 --> 00:01:52,670
Let's say we use the variable k because that's the typical variable that we use for these partition

32
00:01:52,670 --> 00:01:53,240
problems.

33
00:01:53,240 --> 00:01:54,740
Now you can use any other variable.

34
00:01:54,740 --> 00:01:59,450
Now k will take the values from one up to three okay.

35
00:01:59,450 --> 00:02:03,530
Or from I up to j minus one in this case.

36
00:02:03,530 --> 00:02:07,820
So that means that k will take the values one, two and three.

37
00:02:07,820 --> 00:02:12,920
And each of these represent ways of partitioning the array which is given to us.

38
00:02:12,920 --> 00:02:18,380
Now k is equal to one would mean that we partition it over here k is equal to two would mean that we

39
00:02:18,380 --> 00:02:22,340
are partitioning it over here, and k is equal to three would mean that we are partitioning it over

40
00:02:22,340 --> 00:02:22,640
here.

41
00:02:22,640 --> 00:02:23,780
More of that soon.

42
00:02:23,780 --> 00:02:31,940
Now what will happen is for each of these branches we'll find the number of multiplications involved

43
00:02:31,940 --> 00:02:32,540
okay.

44
00:02:33,450 --> 00:02:39,000
And then we'll just have to find the minimum between these three and return that.

45
00:02:39,000 --> 00:02:40,290
So that would be the answer.

46
00:02:40,320 --> 00:02:40,710
Okay.

47
00:02:40,710 --> 00:02:45,270
So that's the high level way that we are going to approach this in a recursive manner.

48
00:02:45,300 --> 00:02:50,100
Now let's just go down this branch over here to see what happens next.

49
00:02:50,100 --> 00:02:53,070
Let's say k is equal to one okay.

50
00:02:53,070 --> 00:02:55,770
So that means we are partitioning it in this manner.

51
00:02:55,770 --> 00:02:59,760
And whenever we are partitioning it notice there are two sides.

52
00:02:59,760 --> 00:03:02,700
So this is side one and this is side two.

53
00:03:02,700 --> 00:03:10,650
And then we'll just have to identify the cost associated with each side and the cost associated with

54
00:03:10,650 --> 00:03:14,910
multiplying the two matrices that will be formed from each side.

55
00:03:14,910 --> 00:03:21,180
Because eventually each side would be just one matrix because for example, notice over here we have

56
00:03:21,180 --> 00:03:22,620
one, two, three matrices.

57
00:03:22,620 --> 00:03:27,360
But then we are going to multiply these matrices and turn them into one matrix.

58
00:03:27,360 --> 00:03:29,460
And over here we have one matrix.

59
00:03:29,460 --> 00:03:33,690
And in this manner ultimately we will just have one matrix on each side.

60
00:03:33,690 --> 00:03:39,090
So there is a cost associated for ensuring that we just have one matrix on each side.

61
00:03:39,090 --> 00:03:41,970
So we'll have to find those respective costs.

62
00:03:41,970 --> 00:03:45,540
And then there is a cost for multiplying these two matrices.

63
00:03:45,540 --> 00:03:51,750
And when k is equal to one we will again recursively call the find cost function to find the number

64
00:03:51,750 --> 00:03:57,360
of multiplications required when we make a partition like this, and to find that, we will have to

65
00:03:57,360 --> 00:04:00,420
add find cost one comma one plus.

66
00:04:00,420 --> 00:04:07,470
Find cost two comma four plus the cost of multiplying these two matrices okay.

67
00:04:07,470 --> 00:04:10,950
So this one over here has the dimensions 20 into ten.

68
00:04:10,950 --> 00:04:16,890
And then once you multiply these three matrices the dimension would be ten into 40 okay.

69
00:04:16,890 --> 00:04:18,450
And again what is this over here.

70
00:04:18,450 --> 00:04:19,890
Find cost one comma one.

71
00:04:19,890 --> 00:04:22,500
That's this part over here or this side right.

72
00:04:22,500 --> 00:04:24,570
Which starts at one and ends at one.

73
00:04:24,570 --> 00:04:32,190
Because k in this case is one and two comma four is this part over here which is k plus one up to j.

74
00:04:32,190 --> 00:04:32,640
Okay.

75
00:04:32,640 --> 00:04:36,420
And again because we've used k over here this is I comma k.

76
00:04:36,420 --> 00:04:38,910
And this is k plus one up to j.

77
00:04:38,910 --> 00:04:45,300
And in this case notice that fine cost one comma one will just return the value zero.

78
00:04:45,330 --> 00:04:52,890
This would be equal to zero because this actually just represents one matrix which has the dimensions

79
00:04:52,890 --> 00:04:54,210
20 into ten.

80
00:04:54,210 --> 00:04:57,300
And there is no cost of multiplication involved.

81
00:04:57,300 --> 00:04:57,660
Okay.

82
00:04:57,660 --> 00:04:59,880
So that's an interesting thing to note over here.

83
00:04:59,880 --> 00:05:07,170
And to find the value of fine cost two comma four, which implies to find the cost or the minimum cost

84
00:05:07,170 --> 00:05:13,800
of the matrices that span from index two up to index four will have to again use another variable like

85
00:05:13,800 --> 00:05:20,340
k, and it will take the values from two up to four minus one, which in this case is equal to three.

86
00:05:20,340 --> 00:05:23,520
So k can take the values two and three.

87
00:05:23,520 --> 00:05:29,010
And in these two scenarios we'll get the cost of multiplying the matrices.

88
00:05:29,010 --> 00:05:33,210
And the minimum of that would be taken just like what we did over here.

89
00:05:33,390 --> 00:05:38,310
So this is the way that we will recursively solve this question.

90
00:05:38,310 --> 00:05:43,770
And I'm just drawing part of the recursive tree because this is an approach that we are already familiar

91
00:05:43,770 --> 00:05:44,190
with.