下面递归实现的斐波那契数列的时间复杂度为 O(2^n)。

def fib_memo(n, memo):
    if n <= 1:
        return n
    if memo[n] != -1:
        return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

if __name__ == "__main__":
    n = 40
    memo = [-1] * 100
    result = fib_memo(n, memo)
    print(result)