def fib(N):
    """
    Avoid redoing the something over and over and store any Fib in a dictionary
    to not do it again
    Time: o(n)
    """
    memo = {}
    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