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

1long long fib_memo(int n, long long memo[]) {2   if (n <= 1) return n;3   if (memo[n] != -1) return memo[n];4   memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);5   return memo[n];6}7 8int main() {9   int n = 40;10   long long memo[100];11   fill_n(memo, 100, -1);12   long long result2 = fib_memo(n, memo);13   return 0;14}