# fibonacci
# time complexity: O(n^2)
# space complexity: O(n)
def fib(n):
    return 1 if n <= 2 else fib(n - 1) + fib(n - 2)


# memoization
# time complexity: O(n)
# space complexity: O(n)
def fib_memo(n, memo={}):
    if n <= 2:
        return 1
    if n in memo:
        result = memo[n]
    result = fib_memo(n - 1, memo[n]) + fib_memo(n - 2, memo[n])
    return result