1
00:00:00,690 --> 00:00:07,290
Previously we have discussed the recursive approach and we have also implemented memoization.

2
00:00:07,320 --> 00:00:14,640
Now let's proceed and discuss the tabulation or bottom up approach for the Fibonacci question.

3
00:00:15,300 --> 00:00:17,970
Now for this, let's take an example.

4
00:00:17,970 --> 00:00:24,420
Let's say we are trying to find f of five, or we're trying to find the Fibonacci number where n is

5
00:00:24,420 --> 00:00:25,710
equal to five.

6
00:00:25,740 --> 00:00:29,700
Now, as the name suggests over here which is tabulation.

7
00:00:29,700 --> 00:00:33,390
So in this approach we typically use a table.

8
00:00:33,390 --> 00:00:41,010
And it can be either a one dimensional table or a two dimensional table based on the question at hand.

9
00:00:41,010 --> 00:00:45,330
So for the Fibonacci question we are going to keep it very simple.

10
00:00:45,330 --> 00:00:49,890
And we just need a one dimensional table because this is a very easy question.

11
00:00:49,890 --> 00:00:52,740
So over here we have a 1D table.

12
00:00:52,740 --> 00:00:59,010
And because we want to find f of five over here I have indices from zero up to five.

13
00:00:59,400 --> 00:01:06,990
It's also given in the question that when n is equal to zero, the value in the Fibonacci series is

14
00:01:06,990 --> 00:01:10,590
zero, and when n is equal to one, the value is one.

15
00:01:10,590 --> 00:01:13,020
So we already have these two values.

16
00:01:13,020 --> 00:01:20,880
And then we will just iterate through this table over here and fill the values over here and over here

17
00:01:20,880 --> 00:01:22,470
and over here and over here.

18
00:01:22,470 --> 00:01:29,640
Also notice that when we were filling the values in this table over here, we were able to set the initial

19
00:01:29,640 --> 00:01:35,430
conditions of the table using the base case in our recursive solution.

20
00:01:35,430 --> 00:01:43,140
So typically the base case in the recursive solution will give us the initial conditions for the tabulation

21
00:01:43,140 --> 00:01:44,640
or bottom up approach.

22
00:01:44,640 --> 00:01:47,580
Now let's go ahead and see how this works out.

23
00:01:47,580 --> 00:01:49,830
So initially we have these two values.

24
00:01:49,830 --> 00:01:52,950
Now we are iterating from two up to five.

25
00:01:52,950 --> 00:01:59,160
So in this case we will just add these two together to get the value over here which is zero plus one

26
00:01:59,160 --> 00:02:00,570
which is one itself.

27
00:02:00,570 --> 00:02:06,030
Then we come over here and to get the value over here we're going to add these two values.

28
00:02:06,030 --> 00:02:08,670
That's one plus one which is equal to two.

29
00:02:08,670 --> 00:02:16,050
And in a similar manner to get the value at n is equal to four, we will add one and two which is equal

30
00:02:16,050 --> 00:02:16,620
to three.

31
00:02:16,620 --> 00:02:20,100
And then we will add two and three which is equal to five.

32
00:02:20,100 --> 00:02:23,910
And we get our answer and we can just return five.

33
00:02:24,740 --> 00:02:28,190
So this is how the tabulation approach works.

34
00:02:28,190 --> 00:02:36,140
Now in a previous video, we had discussed that it's always easier to implement the tabulation or the

35
00:02:36,140 --> 00:02:42,470
bottom up approach after you've written the recursive solution, especially when you are dealing with

36
00:02:42,470 --> 00:02:48,830
a question that you are not familiar with now, it will become more clear in more difficult questions

37
00:02:48,830 --> 00:02:56,270
as to why this is the case, or why it's helpful to first write the recursive solution before attempting

38
00:02:56,300 --> 00:02:58,820
to write the tabulation or bottom up approach.

39
00:02:58,820 --> 00:03:04,520
But over here, because the question itself is very easy and it's defined, the relationship is given

40
00:03:04,520 --> 00:03:09,440
to us that f of n is equal to f of n minus one plus f of n minus two.

41
00:03:09,470 --> 00:03:12,560
You may feel that you could have written this directly.

42
00:03:12,650 --> 00:03:18,140
That's because this question is pretty easy, but we will see the benefit of first writing the recursive

43
00:03:18,140 --> 00:03:21,260
solution in future questions, which are more difficult.

44
00:03:21,290 --> 00:03:26,990
Now let's proceed, and let's take a look at the complexity analysis of this solution.