1
00:00:00,510 --> 00:00:06,990
Previously, we have discussed the recursive approach for solving the Fibonacci question.

2
00:00:07,350 --> 00:00:14,640
In this video, let's get started with the memoization approach or the top down approach for solving

3
00:00:14,640 --> 00:00:15,360
this question.

4
00:00:15,390 --> 00:00:19,620
Now remember memoization is just recursion plus storage.

5
00:00:19,620 --> 00:00:26,550
So as we have already written the recursive approach of solving this question, we just need to modify

6
00:00:26,550 --> 00:00:30,180
it a bit to ensure that we store what we compute.

7
00:00:30,180 --> 00:00:36,060
So you will see that we will just need to add a few lines of code to the solution that we have already

8
00:00:36,060 --> 00:00:38,730
written to come up with the memoization approach.

9
00:00:38,730 --> 00:00:40,170
So let's get started.

10
00:00:40,290 --> 00:00:46,650
So over here we have the recursion tree for finding f of five that we have seen so many times.

11
00:00:46,680 --> 00:00:52,020
Now what we will do is we will have a hash table or a dictionary.

12
00:00:52,020 --> 00:00:59,670
And whenever we need to find let's say f of five or f of four or f of three, what we will do is before

13
00:00:59,670 --> 00:01:04,440
we go ahead and recursively call the same function with lower input.

14
00:01:04,440 --> 00:01:10,890
First we will check whether this value that we need is there in the dictionary or hash table.

15
00:01:10,890 --> 00:01:14,820
And if it's not there, then only we will compute it.

16
00:01:14,820 --> 00:01:19,530
And once we compute it, we will store it or add it to the hash table.

17
00:01:19,530 --> 00:01:21,540
So this is the approach that we will take.

18
00:01:21,540 --> 00:01:24,570
So initially we are trying to find f of five.

19
00:01:24,570 --> 00:01:26,340
So let's trace the algorithm.

20
00:01:26,340 --> 00:01:30,300
We will check whether f of five is there in the hash table.

21
00:01:30,300 --> 00:01:32,730
And we will see that it's not there.

22
00:01:33,240 --> 00:01:36,030
If it was there we would have just returned the value.

23
00:01:36,030 --> 00:01:37,770
But again we are just starting out.

24
00:01:37,770 --> 00:01:45,510
So because it's not there, we will go ahead and we will find F of five by finding f of four and f of

25
00:01:45,510 --> 00:01:45,960
three.

26
00:01:45,960 --> 00:01:50,220
And once we get the value, we will store it in the hash table.

27
00:01:50,220 --> 00:01:53,070
So let's draw the hash table over here.

28
00:01:54,630 --> 00:02:02,730
Initially notice that in the hash table we will have the values zero and one for n, because these are

29
00:02:02,730 --> 00:02:04,410
values that are already given to us.

30
00:02:04,410 --> 00:02:10,320
In the question, we know that when n is equal to zero, f of zero is zero, and when n is equal to

31
00:02:10,320 --> 00:02:11,940
one, f of one is one.

32
00:02:11,940 --> 00:02:16,050
So these values are already there in the hash table or the dictionary.

33
00:02:16,050 --> 00:02:17,370
And then we proceed.

34
00:02:17,370 --> 00:02:19,410
We are calculating f of four.

35
00:02:19,410 --> 00:02:23,550
And again we'll check is f of four in the hash table.

36
00:02:23,550 --> 00:02:25,710
It's not there in the hash table.

37
00:02:25,710 --> 00:02:30,210
So we have to again go ahead and calculate f of three.

38
00:02:30,420 --> 00:02:33,630
We will see whether f of three is in the hash table.

39
00:02:33,630 --> 00:02:36,150
We see that it's not there in the hash table.

40
00:02:36,150 --> 00:02:38,940
So we go ahead and calculate f of two.

41
00:02:39,980 --> 00:02:42,890
Now we will check is f of two in the hash table.

42
00:02:42,890 --> 00:02:45,200
We see that it's not there in the hash table.

43
00:02:45,200 --> 00:02:47,570
So we proceed down this branch.

44
00:02:47,570 --> 00:02:52,400
We go to f of one and we'll check is f of one in the hash table.

45
00:02:52,400 --> 00:02:58,130
And we see that yes f of one is there or n is equal to one is there in the hash table.

46
00:02:58,130 --> 00:03:00,590
So we will just return the value one.

47
00:03:01,100 --> 00:03:04,190
So this over here will return the value one.

48
00:03:05,780 --> 00:03:08,420
And then it will go down this branch.

49
00:03:08,420 --> 00:03:14,330
So we will check f of zero and we'll see that it's also there in the hash table.

50
00:03:14,330 --> 00:03:17,420
So this also will return the value zero.

51
00:03:18,600 --> 00:03:24,570
Now we get the value of f of two because we have the value of f of one and f of zero.

52
00:03:24,570 --> 00:03:29,850
So we add these two together to get zero plus one which is equal to one.

53
00:03:29,850 --> 00:03:32,070
So f of two is equal to one.

54
00:03:32,070 --> 00:03:37,530
And once we have computed this we will store it in the hash table.

55
00:03:37,530 --> 00:03:41,220
So over here for n is equal to two the value is one.

56
00:03:41,220 --> 00:03:42,390
So we store this.

57
00:03:42,390 --> 00:03:45,240
Then this over here will return.

58
00:03:45,750 --> 00:03:53,430
And then when this branch is explored for F of one, we see that we already have this value, and therefore

59
00:03:53,430 --> 00:04:01,650
this will return the value which is one, and thus f of three is calculated which is one plus one,

60
00:04:01,650 --> 00:04:03,300
and that's equal to two.

61
00:04:03,330 --> 00:04:06,000
So we get the value of f of three as two.

62
00:04:06,000 --> 00:04:07,740
And we store this.

63
00:04:08,420 --> 00:04:09,860
In the hash table.

64
00:04:09,980 --> 00:04:14,000
So we have over here for n is equal to three the value is two.

65
00:04:14,000 --> 00:04:15,860
And then this returns okay.

66
00:04:15,860 --> 00:04:17,780
So this returns the value two.

67
00:04:17,780 --> 00:04:22,040
And then we explore this branch over here and over here.

68
00:04:22,040 --> 00:04:25,760
We just want the value of f of two.

69
00:04:26,630 --> 00:04:28,820
So we want the value of f of two.

70
00:04:28,820 --> 00:04:31,190
But notice that we already have it.

71
00:04:31,190 --> 00:04:34,340
So we don't need to go down these paths.

72
00:04:34,340 --> 00:04:38,810
We can directly return the value which is equal to one.

73
00:04:38,810 --> 00:04:40,760
So this over here will return one.

74
00:04:40,760 --> 00:04:47,150
And in this manner we will be able to calculate the value of f of four which is two plus one which is

75
00:04:47,150 --> 00:04:47,690
three.

76
00:04:47,690 --> 00:04:51,980
And once we get this we store it in the hash table.

77
00:04:51,980 --> 00:04:54,890
So we have got the value of f of four as well.

78
00:04:54,890 --> 00:04:57,890
And this returns the value three.

79
00:04:57,890 --> 00:05:04,100
And then when we go down this branch and when we try to find the value of f of three, we see that we

80
00:05:04,100 --> 00:05:06,590
already have it in our hash table.

81
00:05:06,590 --> 00:05:09,380
So we will directly return the value two.

82
00:05:09,380 --> 00:05:12,530
And thus f of five will be calculated, which is.

83
00:05:13,210 --> 00:05:15,970
Three plus two, which is equal to five.

84
00:05:16,090 --> 00:05:19,120
And once we get it, we store it in the hash table.

85
00:05:19,120 --> 00:05:23,290
So notice that because over here we already had calculated f of three.

86
00:05:23,290 --> 00:05:26,740
We did not have to do these calls.

87
00:05:27,220 --> 00:05:34,660
So this is why memoization has much better time complexity than a simple recursive approach.

88
00:05:34,690 --> 00:05:36,310
So this is how it works.

89
00:05:36,310 --> 00:05:39,730
And we were able to find the value of f of five.

90
00:05:39,760 --> 00:05:47,500
Now the good thing over here is that we are able to retrieve a value from the dictionary or hash table

91
00:05:47,500 --> 00:05:49,990
in constant time when we have the key.

92
00:05:50,020 --> 00:05:54,010
So for example over here for f of three the key is three.

93
00:05:54,160 --> 00:06:00,610
And because we have the key we can access the value of f of three which is this value over here which

94
00:06:00,610 --> 00:06:02,710
is two at constant time.

95
00:06:02,710 --> 00:06:07,810
So this is what helps us to significantly improve the time complexity.

96
00:06:07,810 --> 00:06:13,270
Let's now go ahead and code the solution that we have discussed over here, which is the memoization

97
00:06:13,270 --> 00:06:13,960
approach.