Codility - Lesson 13 Fibonacci Numbers

Source Link:
https://codility.com/programmers/lessons/13-fibonacci_numbers/

Some Notes: 
The first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.



The first twelve Fibonacci numbers are:



Notice that recursive enumeration as described by the definition is very slow.

Enumeration of the Fibonacci numbers can be done faster simply by using a basis of dynamic programming. 

We can calculate the values F0, F1, . . . ,Fn based on the previously calculated numbers (it is sufficient to remember only the last two values).

13.2: Finding Fibonacci numbers dynamically.
1 def fibonacciDynamic(n):
2 fib = [0] * (n + 2)
3 fib[1] = 1
4 for i in xrange(2, n + 1):
5 fib[i] = fib[i - 1] + fib[i - 2]
6 return fib[n]

The time complexity of the above algorithm is O(n).