Previously we have discussed the recursive approach and we have also implemented memoization.
Now let's proceed and discuss the tabulation or bottom up approach for the Fibonacci question.
Now for this, let's take an example.
Let's say we are trying to find f of five, or we're trying to find the Fibonacci number where n is
equal to five.
Now, as the name suggests over here which is tabulation.
So in this approach we typically use a table.
And it can be either a one dimensional table or a two dimensional table based on the question at hand.
So for the Fibonacci question we are going to keep it very simple.
And we just need a one dimensional table because this is a very easy question.
So over here we have a 1D table.
And because we want to find f of five over here I have indices from zero up to five.
It's also given in the question that when n is equal to zero, the value in the Fibonacci series is
zero, and when n is equal to one, the value is one.
So we already have these two values.
And then we will just iterate through this table over here and fill the values over here and over here
and over here and over here.
Also notice that when we were filling the values in this table over here, we were able to set the initial
conditions of the table using the base case in our recursive solution.
So typically the base case in the recursive solution will give us the initial conditions for the tabulation
or bottom up approach.
Now let's go ahead and see how this works out.
So initially we have these two values.
Now we are iterating from two up to five.
So in this case we will just add these two together to get the value over here which is zero plus one
which is one itself.
Then we come over here and to get the value over here we're going to add these two values.
That's one plus one which is equal to two.
And in a similar manner to get the value at n is equal to four, we will add one and two which is equal
to three.
And then we will add two and three which is equal to five.
And we get our answer and we can just return five.
So this is how the tabulation approach works.
Now in a previous video, we had discussed that it's always easier to implement the tabulation or the
bottom up approach after you've written the recursive solution, especially when you are dealing with
a question that you are not familiar with now, it will become more clear in more difficult questions
as to why this is the case, or why it's helpful to first write the recursive solution before attempting
to write the tabulation or bottom up approach.
But over here, because the question itself is very easy and it's defined, the relationship is given
to us that f of n is equal to f of n minus one plus f of n minus two.
You may feel that you could have written this directly.
That's because this question is pretty easy, but we will see the benefit of first writing the recursive
solution in future questions, which are more difficult.
Now let's proceed, and let's take a look at the complexity analysis of this solution.