1
00:00:00,370 --> 00:00:01,180
All right.

2
00:00:01,180 --> 00:00:02,050
Welcome back.

3
00:00:02,050 --> 00:00:06,490
So we are done discussing the recursive approach for solving this question.

4
00:00:06,490 --> 00:00:11,200
Now let's take a look at how we can implement the memoization approach.

5
00:00:11,200 --> 00:00:16,720
And for this we'll just need to add a few lines of code to the recursive approach that we have already

6
00:00:16,720 --> 00:00:17,530
implemented.

7
00:00:17,530 --> 00:00:20,560
So let's get started with the memoization approach.

8
00:00:20,710 --> 00:00:26,530
We have already drawn out the recursive tree or part of the recursive tree in previous videos.

9
00:00:26,530 --> 00:00:28,480
And this is how it looked like.

10
00:00:28,480 --> 00:00:32,200
Let's say you had an array which had five elements.

11
00:00:32,200 --> 00:00:36,160
So the indices involved would go from zero up to four.

12
00:00:36,160 --> 00:00:42,340
And over here when we call the find cost function for the first time, we'll pass the index one and

13
00:00:42,340 --> 00:00:48,970
four, which means that we're trying to find the cost of multiplying all the matrices that can be formed

14
00:00:48,970 --> 00:00:51,910
starting at index one and going up to index four.

15
00:00:51,910 --> 00:00:55,000
And then we have already discussed how we take another variable k.

16
00:00:55,000 --> 00:00:57,340
We make all the different possible partitions.

17
00:00:57,340 --> 00:01:04,420
And we find the partition that gives us the minimum cost for multiplying all the matrices involved.

18
00:01:04,420 --> 00:01:11,920
Now first let's discuss how does this become a question where possibly memoization can help?

19
00:01:11,920 --> 00:01:16,810
Or in other words, how do we identify this as a possible candidate for memoization?

20
00:01:16,810 --> 00:01:22,720
When you take a look at the recursive tree, notice you have multiple branches over here.

21
00:01:22,720 --> 00:01:30,100
And we have previously discussed that in these type of scenarios, there is a high likelihood for overlapping

22
00:01:30,100 --> 00:01:31,240
subproblems.

23
00:01:31,240 --> 00:01:38,380
Now to take a more detailed view and to actually see that there are overlapping subproblems, let's

24
00:01:38,380 --> 00:01:42,130
try to draw out the recursive tree or part of the recursive tree.

25
00:01:42,130 --> 00:01:44,290
And let's just consider the indices.

26
00:01:44,290 --> 00:01:50,950
So the indices involved in the array which is given to us start at index zero and goes up to index four.

27
00:01:50,950 --> 00:01:56,710
And we have already seen that the first time we call the find cost function the indices passed are one

28
00:01:56,710 --> 00:01:57,460
comma four.

29
00:01:57,460 --> 00:01:59,800
Now the tree would look like this okay.

30
00:01:59,800 --> 00:02:02,620
So you start with the indices one comma four.

31
00:02:02,620 --> 00:02:06,640
And then the possibilities are that k can take the values 1 to 3.

32
00:02:06,640 --> 00:02:13,540
And when k takes the value one, you partition it in a way that one side goes from 1 to 1 and the other

33
00:02:13,540 --> 00:02:15,100
side goes from 2 to 4.

34
00:02:15,100 --> 00:02:20,830
Okay, now to find the answer to this subproblem, k can take the values two and three.

35
00:02:20,830 --> 00:02:25,060
Or there are these two ways of partitioning this subarray okay.

36
00:02:25,060 --> 00:02:29,950
And again when k is equal to two the parts are two comma two and three comma four.

37
00:02:29,950 --> 00:02:35,500
And when k is equal to three, the different parts of the two sides are two comma three and four comma

38
00:02:35,500 --> 00:02:35,950
four.

39
00:02:35,950 --> 00:02:36,370
Okay.

40
00:02:36,370 --> 00:02:39,130
And again this is just part of the recursive tree.

41
00:02:39,130 --> 00:02:43,210
Now notice that three comma four occurs two times okay.

42
00:02:43,210 --> 00:02:45,760
You have it over here and you have it over here.

43
00:02:45,760 --> 00:02:53,740
Now when you did compute this if we had stored it, then when we encounter this part we could just retrieve

44
00:02:53,740 --> 00:02:56,920
it without actually going ahead and computing it again.

45
00:02:56,920 --> 00:02:57,340
Right.

46
00:02:57,340 --> 00:03:02,500
So again, that's what we imply with overlapping subproblems in a similar way you have four comma four

47
00:03:02,500 --> 00:03:03,700
over here and here.

48
00:03:03,700 --> 00:03:09,370
And you will see that there are multiple overlapping subproblems if you draw out the complete recursive

49
00:03:09,400 --> 00:03:09,790
tree.

50
00:03:09,790 --> 00:03:14,800
And again four comma four is technically something that we will not compute because these two are equal.

51
00:03:14,800 --> 00:03:19,660
But again, I'm just showing it over here to indicate that things are in fact repeating.

52
00:03:19,660 --> 00:03:23,890
So in this question there are overlapping subproblems.

53
00:03:23,890 --> 00:03:30,430
And the second thing is that in this question there is optimal substructure, because we can use the

54
00:03:30,430 --> 00:03:33,520
solution to a subproblem to solve the problem okay.

55
00:03:33,520 --> 00:03:34,840
And again what does that mean.

56
00:03:34,840 --> 00:03:42,430
It means that for example, if we know the answer to two comma four, we can use this to find this answer

57
00:03:42,430 --> 00:03:45,100
where k is equal to one for one comma four okay.

58
00:03:45,100 --> 00:03:48,970
And if we know these we can find the answer to this.

59
00:03:48,970 --> 00:03:53,710
Similarly if we know these we can find the answer to this okay for these three versions.

60
00:03:53,710 --> 00:03:59,710
So it means that we are able to use the solution to subproblems to solve the problem.

61
00:03:59,710 --> 00:04:02,950
And that means that this question has optimal substructure.

62
00:04:02,950 --> 00:04:09,190
Now because this question has both overlapping subproblems and optimal substructure, it's an ideal

63
00:04:09,190 --> 00:04:11,230
candidate for dynamic programming.

64
00:04:11,230 --> 00:04:16,480
And that's why we can solve this question or optimize this question using memoization.

65
00:04:16,480 --> 00:04:17,050
All right.

66
00:04:17,050 --> 00:04:22,210
So getting back to the question, we have already seen how the recursive tree looks like.

67
00:04:22,210 --> 00:04:25,750
And we have already seen how to recursively solve the question.

68
00:04:25,750 --> 00:04:31,180
Now memoization is just about storing stuff and then avoiding recomputing.

69
00:04:31,180 --> 00:04:31,510
Right.

70
00:04:31,510 --> 00:04:37,870
So after we check the base case which is over here, and before we go ahead and compute this part,

71
00:04:37,870 --> 00:04:44,650
which is the recursive case, we will first check whether we have already computed this particular combination

72
00:04:44,650 --> 00:04:45,790
of I and J.

73
00:04:45,790 --> 00:04:52,720
And if we had computed it previously, we would just return it, and if not, we'll go ahead and compute

74
00:04:52,720 --> 00:04:52,900
it.

75
00:04:52,900 --> 00:04:58,750
And this time we would store it so that if we encounter this again in the future, we will not require

76
00:04:58,750 --> 00:04:59,800
to recompute it.

77
00:04:59,940 --> 00:05:02,490
So this is all that memoization is about.

78
00:05:02,490 --> 00:05:05,430
Now let's see how we actually go about doing this.

79
00:05:05,430 --> 00:05:11,010
Now for this, let's say that the array which is given to us is again this array which has five elements.

80
00:05:11,010 --> 00:05:18,360
And for the memoization approach over here, we will need a two dimensional array which will be of size

81
00:05:18,360 --> 00:05:19,350
n into n.

82
00:05:19,350 --> 00:05:26,010
So notice in this case because we have five elements we have five columns and five rows okay.

83
00:05:26,010 --> 00:05:31,470
So the indices of the rows and columns span from zero and go up to four.

84
00:05:31,740 --> 00:05:40,200
And in each cell we would store the cost for multiplying the matrices that can be formed that span from

85
00:05:40,200 --> 00:05:44,160
the particular row index up to the particular column index.

86
00:05:44,160 --> 00:05:51,600
For example, this cell over here will store the cost of multiplying the arrays that can be formed starting

87
00:05:51,600 --> 00:05:54,270
at index two and going up to index four.

88
00:05:54,270 --> 00:05:58,860
And in this example that would be the matrices ten into 30.

89
00:06:00,660 --> 00:06:04,950
30 into five and five into 40.

90
00:06:04,980 --> 00:06:11,730
Okay, so this cell over here will store the minimum number of multiplications required to multiply

91
00:06:11,730 --> 00:06:13,350
these three matrices.

92
00:06:13,350 --> 00:06:14,610
So that's about it.

93
00:06:14,640 --> 00:06:20,550
Now when we take a look at the code you will see that this is just the recursive approach with storing

94
00:06:20,550 --> 00:06:22,290
stuff in this DP table.

95
00:06:22,290 --> 00:06:22,800
That's it.

96
00:06:22,800 --> 00:06:26,670
So it's going to be just a few lines of code a few tweaks here and there.

97
00:06:26,670 --> 00:06:30,900
And we would have converted the recursive approach to the memoization approach.