# naive recursive
def fib(n):
    if n <= 2: 
        f = 1
    else: 
        f = fib(n-1) + fib(n-2)
    return f

print([fib(n) for n in range(1, 10)])

# dynamic programming = recursion + memoization 
memo = {} # {1:1, 2:1, 3:2, 4:3, 5:5, 6:8, 7:13, 8:21, 9:34}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 2: 
        f = 1
    else: 
        f = fib(n-1) + fib(n-2)
    memo[n] = f
    return f

print([fib(n) for n in range(1, 10)])

# bottom-up DP algorithm
memo = {} # {1:1, 2:1, 3:2, 4:3, 5:5, 6:8, 7:13, 8:21, 9:34}
def fib(n):
    for k in range(1, n+1):
        if k <= 2:
            f = 1
        else:
            f = memo[k-1] + memo[k-2]
        memo[k] = f
    return memo[n]
            
print([fib(n) for n in range(1, 10)])