# recursion
def fib(n):
    if n <= 1:
        return n

    return fib(n-1) + fib(n-2)

# recursion with memoization
def fib_memo(n, lookup=None):
    """
    Memoization will continue to take on the overheard of function invocations
    """
    if lookup is None:
        lookup = [None]*(n+1)

    if n is 0 or n is 1:
        lookup[n] = n

    if lookup[n] is None:
        lookup[n] = fib_memo(n-1, lookup) + fib_memo(n-2, lookup)

    return lookup[n]

# iterative DP
def fib_dyn(n):
    """
    Utilizes tabulation
    - Note that the difference between the memoization solution is the absence of repeated function calls and its overhead
    """
    table    = [0] * (n+1)
    table[1] = 1

    for i in range(2, n+1):
        table[i] = table[i-1] + table[i-2]

    return table[n]