1
00:00:00,140 --> 00:00:05,090
Let's now write the tabulation approach for solving the Fibonacci question.

2
00:00:05,090 --> 00:00:07,490
Now for this we will need a DP array.

3
00:00:07,490 --> 00:00:11,840
So let me say let DP is equal to mu array.

4
00:00:13,310 --> 00:00:18,470
And this array will have the values going from zero up to n.

5
00:00:18,470 --> 00:00:24,050
So therefore the size of this array is going to be n plus one okay.

6
00:00:24,050 --> 00:00:31,460
And we will fill initially each cell in this array with the value zero okay.

7
00:00:31,910 --> 00:00:39,350
Now what we will do is we will fill the position zero or the index zero in the DP array with the value

8
00:00:39,350 --> 00:00:39,740
zero.

9
00:00:39,740 --> 00:00:42,620
So I can say dp at zero is equal to zero.

10
00:00:43,160 --> 00:00:49,400
And if n is greater than zero, then I will fill dp at one to be equal to one.

11
00:00:49,400 --> 00:00:56,840
Okay, so if n is greater than zero we can say dp at one is equal to one.

12
00:00:56,840 --> 00:00:58,940
Now why do I have this condition over here.

13
00:00:58,940 --> 00:01:01,370
Like if n is equal to zero.

14
00:01:01,370 --> 00:01:05,330
And if I try to access dp at one over here, then it will fail, right?

15
00:01:05,330 --> 00:01:12,110
Because if n is equal to zero, then the dp array would just have one element, or its size would be

16
00:01:12,110 --> 00:01:14,750
just one and there would be no DP at one.

17
00:01:14,750 --> 00:01:16,760
So that's why I have this check over here.

18
00:01:16,760 --> 00:01:21,590
So if n is greater than zero, then we set dp at one to be equal to one.

19
00:01:21,800 --> 00:01:24,320
After that we will need a count variable.

20
00:01:24,320 --> 00:01:31,700
So let us say let count is equal to one and we will have a while loop that goes on as long as count

21
00:01:31,700 --> 00:01:38,210
is less than n, and when count is equal to n, we will come out of the while loop and then we will

22
00:01:38,210 --> 00:01:39,920
just return depee at n.

23
00:01:40,010 --> 00:01:42,320
So this is how we are going to approach this.

24
00:01:42,320 --> 00:01:48,380
And inside the while loop over here, we will just keep calculating the next value in the DP array.

25
00:01:48,380 --> 00:01:51,770
So we will say count plus is equal to one.

26
00:01:51,770 --> 00:01:53,090
So we incrementing count.

27
00:01:53,090 --> 00:01:56,570
So as of now let us say the value of n is three for example.

28
00:01:56,570 --> 00:01:58,880
So we know dp at zero and dp at one.

29
00:01:58,880 --> 00:02:04,130
And we have set count to equal one because we know the value up to one which is this one over here.

30
00:02:04,130 --> 00:02:06,230
And over here we are incrementing count.

31
00:02:06,230 --> 00:02:08,210
So count becomes equal to two.

32
00:02:08,210 --> 00:02:14,030
And we will say dp at count, which for the example that I was discussing is dp at two.

33
00:02:14,030 --> 00:02:19,730
And that would be dp at count minus one plus dp at count minus two.

34
00:02:19,730 --> 00:02:21,650
Because that's the Fibonacci property right?

35
00:02:21,650 --> 00:02:24,890
FIB n is equal to five n minus one plus fib n minus two.

36
00:02:24,920 --> 00:02:27,350
So we are calculating dp at count.

37
00:02:27,350 --> 00:02:29,090
And then again we come over here.

38
00:02:29,090 --> 00:02:32,390
So if count is less than n we again increment count.

39
00:02:32,390 --> 00:02:35,060
And we calculate the new dp of count.

40
00:02:35,060 --> 00:02:39,230
And when count becomes equal to n we come out of this.

41
00:02:39,230 --> 00:02:43,370
So that would mean that we have already calculated dp at n.

42
00:02:43,370 --> 00:02:46,730
And then we come over here and we return dp at n.

43
00:02:46,730 --> 00:02:49,730
So this is the tabulation approach for solving this question.

44
00:02:49,730 --> 00:02:53,870
Now let's go ahead and run this code and see if it's passing all the test cases.

45
00:02:54,560 --> 00:02:57,440
And you can see that it's passing all the test cases.

46
00:02:57,440 --> 00:03:03,830
Now again let me remind you do make use of the user logs which are provided for each test case in case

47
00:03:03,830 --> 00:03:07,580
you are stuck at some point and you want some help to debug your code.