Fibonacci number using Dynamic Programming

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.

For the above mentioned solution Time complexity is linear i.e. O(n) .