Fibonacci series solution using dynamic programming.
What is the Fibonacci series/number?
It's a series of numbers where the first and second numbers are 0 and 1 respectively, and the following number is the sum of the last two numbers.
0 1 1 2 3 5 8 13 21 34 55 89 144 …
Program to print the first 10 numbers in the Fibonacci series.
The time and space complexity of the below code will be O(n) & O(1)
Usually, in interviews and in competitive programming we don’t get asked to print the first n numbers of the Fibonacci series, rather then the most common question is
“To Print The Number Which Comes On The Kth position in the Fibonacci series”
Example to print the number which comes at 11th position in the Fibonacci series. And the answer for that will be 89 assuming we are counting the numbers from index 0.
Now there are a lot of ways to do that with of course different time and space complexities, I will cover most of the main efficient solutions.
Let's jump into the code then.
Solution 1
In the above code, we are solving the problem in a recursive way. In line 2 we have declared our base case which will be, if n == 0 return 0 or if n == 1 return 1 because as we know the first two numbers in the Fibonacci series are 0 and 1 or we can also say for f(0) it will be 0 and for f(1) it will be 1.
And the time complexity of the below code will be O(2^n)
because as we go down into the recursion tree, at each level for each n we have to find 2 numbers (because in order to get the number K we have to know the k-1 and k-2 number first). So as we go down into the tree we are multiplying the rate of operations by 2 at each level.
Which we can also write as O(2^n).
And as for the space complexity, it's going to be linear i.e. O(n) as we are maintaining the stack of a pending receive function calls, and at max, this stack will have n stack call in it.
Solution using dynamic programming.
Solution 2 using Memoization
In the above code, we are again using recursion almost in the same way, but we are also maintaining an array of size n. Which will store the values of any f(n) once we calculate its value so that we don’t have to recalculate it again. Thus helping us to stop overlapping or recalculating sub-problems again.
If we see the above recursion tree example of f(7), you can see that both in the left part and right part of the tree we are recalculating the subproblems again which by the way is called overlapping. Like for f(5) in the left and again f(5) in the right part of the tree. But since we are maintaining an array that will store the values of f(n) once we calculate its values we don’t have to find its values again which eventual helps us to reduce the time complexity from O(2^n) to O(n), and which of course is a big jump.
And for the space complexity, it will be O(2n) since we are also maintaining an array but as per the big O rule, we drop the constants so O(n) will be the final value.
Solution 3 using Tabulation
The above solution is totally using the Memoization method but instant of recursion it's using a loop which will run n times, thus already giving you the idea of time complexity this code will take and i.e O(n).
And for the space complexity this time it will be only O(n) because we are only maintaining an array.
which we can also improve by removing the array from the code, see the below code snippet.
In the first code snippet, if you carefully notice there is a patter being followed on each iteration of the loop, i.e. we are recalculating the next values by the last two values, and the remaining array just remains like that we don’t check the remaining element in an array at all, so instead of storing all the unnecessary items in an array, why not to store the last two elements in a variable, thus helping us to achieve the constant space complexity i.e. O(1).
Here is the full code spinnet of the above example you can just directly copy & paste it into any java compiler and test the example yourself.
If you learned anything from this article please press that follow button if not already🚗.
