1
00:00:00,080 --> 00:00:05,840
Let's now write the code for the memoization approach that we have discussed in the previous video for

2
00:00:05,840 --> 00:00:07,760
solving the Fibonacci question.

3
00:00:07,790 --> 00:00:08,420
All right.

4
00:00:08,420 --> 00:00:11,060
So for this we will use a hash table.

5
00:00:11,060 --> 00:00:12,740
So let's just call it memo.

6
00:00:12,740 --> 00:00:21,170
And in memo I will initially itself add two key value pairs because we know that if n is equal to zero

7
00:00:21,170 --> 00:00:23,630
then fib of n is zero.

8
00:00:23,630 --> 00:00:26,030
And if n is equal to one, fib of one is one.

9
00:00:26,030 --> 00:00:27,680
So we know these two cases.

10
00:00:27,680 --> 00:00:30,500
So let's add that to the memo table.

11
00:00:30,530 --> 00:00:34,880
Okay so I can say over here zero for zero it's zero.

12
00:00:34,880 --> 00:00:36,830
And for one it's one.

13
00:00:36,860 --> 00:00:37,460
All right.

14
00:00:37,760 --> 00:00:40,010
Now we will need a helper function.

15
00:00:40,010 --> 00:00:43,820
Let's just call it calculate fib okay.

16
00:00:46,210 --> 00:00:49,420
And to this function we will be passing a number.

17
00:00:50,090 --> 00:00:53,780
And it will return the Fibonacci of that particular number.

18
00:00:53,780 --> 00:00:55,550
But let's write the details later.

19
00:00:55,550 --> 00:01:01,910
And finally we will be just returning calculate fib and we will pass to it n, which is what we have

20
00:01:01,910 --> 00:01:02,540
over here.

21
00:01:02,540 --> 00:01:05,840
So this is the skeleton of the approach that we are going to take for this.

22
00:01:05,840 --> 00:01:13,070
And inside the helper function, before we go ahead and calculate the Fibonacci number, we will check

23
00:01:13,070 --> 00:01:16,010
whether we had already calculated it previously.

24
00:01:16,400 --> 00:01:16,820
Okay.

25
00:01:16,820 --> 00:01:22,370
So for that we will check whether the key num is present in memo or not.

26
00:01:22,370 --> 00:01:31,220
So I can say if memo and num is not equal to undefined, because if it is not there, then it would

27
00:01:31,220 --> 00:01:33,050
just num would be undefined.

28
00:01:33,050 --> 00:01:39,650
So if memo and num is not equal to undefined, it means that we have already previously calculated this

29
00:01:39,650 --> 00:01:42,830
and stored it in the hash table over here.

30
00:01:42,830 --> 00:01:48,830
And in that case we don't need to recompute it, but rather we will just retrieve it and return it.

31
00:01:48,830 --> 00:01:53,570
So I will say return memo at num okay.

32
00:01:53,570 --> 00:01:59,120
So the value for this particular key in the hash table would be returned in this case.

33
00:01:59,120 --> 00:02:05,570
But if this is not the case it means that we have not yet calculated and stored the Fibonacci for that

34
00:02:05,570 --> 00:02:08,210
particular number in the hash table over here.

35
00:02:08,210 --> 00:02:12,800
So we will go ahead and calculate it and store it at memo at num.

36
00:02:12,800 --> 00:02:15,410
So I can say memo at num.

37
00:02:16,450 --> 00:02:25,960
Is equal to calculate fib num minus one plus calculate fib num minus two.

38
00:02:26,740 --> 00:02:31,900
Okay, so we have calculated the Fibonacci number for that particular num.

39
00:02:31,900 --> 00:02:34,810
And we are storing it in the hash table over here.

40
00:02:34,810 --> 00:02:38,020
And then we will just return memo at num.

41
00:02:38,290 --> 00:02:38,680
All right.

42
00:02:38,680 --> 00:02:39,370
So that's it.

43
00:02:39,370 --> 00:02:43,540
Now let's go ahead and run this code and see if it's passing all the test cases.

44
00:02:44,350 --> 00:02:44,740
All right.

45
00:02:44,740 --> 00:02:46,720
You can see it's passing all the test cases.

46
00:02:46,720 --> 00:02:50,710
So we have used a memoization object or a hash table over here.