"""Fibonacci series:

0, 1, 1, 2, 3, 5, 8,... 

- Fib(0) = 0
- Fib(1) = 1
- Fib(n) = Fib(n - 1) + Fib(n - 2)
"""

from __future__ import absolute_import
from __future__ import print_function
from __future__ import division


def fibonacci_recur(n):
    """Fibonacci series by recursion.

    - Time complexity: O(2^n); too fast.
    - Space complexity: O(n).
    """
    if n <= 1:
        return n
    else:
        return fibonacci_recur(n - 1) + fibonacci_recur(n - 2)


def fibonacci_memo(n):
    """Fibonacci series by iteration and memoization.

    - Time complexity: O(n).
    - Space complexity: O(n).
    """
    fn_d = {}
    fn_d[0] = 0
    fn_d[1] = 1
    for n in range(2, n + 1):
        fn_d[n] = fn_d[n - 1] + fn_d[n - 2]
    return fn_d[n]


def fibonacci_dp(n):
    """Fibonacci series by iteration in dynamic programming.

    - Time complexity: O(n), like fibonacci_memo().
    - Space complexity: O(1), improving a lot.
    """
    a, b = 0, 1
    for _ in range(n):
        # Add two numbers and then shift position by one.
        a, b = b, a + b
    return a


def main():
    import time
    n = 40
    
    print('{}th number of Fibonacci series:'.format(n))

    start_time = time.time()
    print('By recursion: {}'.format(fibonacci_recur(n)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By memoization: {}'.format(fibonacci_memo(n)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By DP: {}'.format(fibonacci_dp(n)))
    print('Time: {}'.format(time.time() - start_time))


if __name__ == '__main__':
    main()

"""Fibonacci series:

0, 1, 1, 2, 3, 5, 8,... 

- Fib(0) = 0
- Fib(1) = 1
- Fib(n) = Fib(n - 1) + Fib(n - 2)
"""

from __future__ import absolute_import
from __future__ import print_function
from __future__ import division


def fibonacci_recur(n):
    """Fibonacci series by recursion.

    - Time complexity: O(2^n)
    - Space complexity: O(1).
    """
    if n <= 1:
        return n
    else:
        return fibonacci_recur(n - 1) + fibonacci_recur(n - 2)


def _fibonacci_memo(n, memo):
    """Fibonacci series by top-down memoization.

    Time complexity: O(n).
    Space complexity: O(n).
    """
    if memo[n]:
        return memo[n]

    if n <= 1:
        memo[n] = n
    else:
        memo[n] = _fibonacci_memo(n - 1, memo) + _fibonacci_memo(n - 2, memo)
    return memo[n]


def fibonacci_memo(n):
    memo = [None for _ in range(n + 1)]
    return _fibonacci_memo(n, memo)


def fibonacci_dp(n):
    """Fibonacci series by bottom-up dynamic programming.

    - Time complexity: O(n).
    - Space complexity: O(n).
    """
    memo = [None for _ in range(n + 1)]
    memo[0] = 0
    memo[1] = 1
    for n in range(2, n + 1):
        memo[n] = memo[n - 1] + memo[n - 2]
    return memo[n]


def fibonacci_dp2(n):
    """Fibonacci series by bottom-up dynamic programming with min space.

    - Time complexity: O(n).
    - Space complexity: O(1).
    """
    a, b = 0, 1
    for _ in range(n):
        # Add two numbers and then shift position by one.
        a, b = b, a + b
    return a


def main():
    import time
    n = 20
    
    print('{}th number of Fibonacci series:'.format(n))

    start_time = time.time()
    print('By recursion: {}'.format(fibonacci_recur(n)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By memoization: {}'.format(fibonacci_memo(n)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By dynamic programming: {}'.format(fibonacci_dp(n)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By optimized DP: {}'.format(fibonacci_dp(n)))
    print('Time: {}'.format(time.time() - start_time))


if __name__ == '__main__':
    main()

Add fibonacci_memo() by top-down memo & revise time/space complexity