Fibonacci Series : the current number is the sum of previous two number. The Fibonacci series are the numbers in the following integer sequence 0, 1, 1, 2, 3, 5, 8, 13,21…
| Recursive formula for the Fibonacci series for seed 0 & 1 is :|
F(n) = F(n-1) + F(n-2)
Recursive Fibonacci solution has time complexity of O(2^n) which will result in high processing time of the large number.
Fibonacci Dynamic Programming solution
Using Dynamic Programming and Memoization we can significantly improve the performance of our solution. Memoization store the results of sub-problems so that we do not have to solve them again.
static int FibDynamic(int n)
int a = 0, b = 1, c = 0;
// To return the first Fibonacci number
if (n == 0) return a;
for (int i = 2; i <= n; i++)
c = a + b; //store a+b in c
a = b; //assign b to a
b = c; // now assign c to b
For the above mentioned solution Time complexity is linear i.e. O(n) .