"""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(n).
    """
    if n <= 1:
        return n
    else:
        return fibonacci_recur(n - 1) + fibonacci_recur(n - 2)


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

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

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


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


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

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


def fibonacci_dp2(n):
    """Fibonacci series by bottom-up dynamic programming with optimized 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()

@@ -479,17 +479,17 @@
 memo(n, 
-F
+f
 ):%0A    %22
@@ -603,17 +603,17 @@
 %0A    if 
-F
+f
 %5Bn%5D:%0A   
@@ -620,25 +620,25 @@
      return 
-F
+f
 %5Bn%5D%0A%0A    if 
@@ -649,25 +649,25 @@
  1:%0A        
-F
+f
 %5Bn%5D = n%0A    
@@ -676,25 +676,25 @@
 se:%0A        
-F
+f
 %5Bn%5D = _fibon
@@ -710,17 +710,17 @@
 (n - 1, 
-F
+f
 ) + _fib
@@ -738,17 +738,17 @@
 (n - 2, 
-F
+f
 )%0A    re
@@ -744,33 +744,33 @@
 , f)%0A    return 
-F
+f
 %5Bn%5D%0A%0A%0Adef fibona
@@ -782,25 +782,25 @@
 emo(n):%0A    
-F
+f
  = %5BNone for
@@ -849,17 +849,17 @@
 memo(n, 
-F
+f
 )%0A%0A%0Adef 
@@ -1005,17 +1005,17 @@
 %22%22%22%0A    
-F
+f
  = %5BNone
@@ -1042,17 +1042,17 @@
 1)%5D%0A    
-F
+f
 %5B0%5D = 0%0A
@@ -1055,17 +1055,17 @@
 = 0%0A    
-F
+f
 %5B1%5D = 1%0A
@@ -1106,16 +1106,16 @@
     
-F
+f
 %5Bn%5D = 
-F
+f
 %5Bn -
@@ -1120,17 +1120,17 @@
  - 1%5D + 
-F
+f
 %5Bn - 2%5D%0A
@@ -1140,17 +1140,17 @@
  return 
-F
+f
 %5Bn%5D%0A%0A%0Ade

Revise memo array from F to f