使用记忆化递归（也称为缓存递归）可以显著提高斐波那契数列的计算效率。这种方法通过将已经计算过的结果存储在一个数组中，从而避免重复计算。

以下是使用记忆化技术改进的斐波那契数列 C++ 代码示例：

#include <iostream>
#include <vector>

// 记忆化数组
std::vector<int> memo;

int fibonacci(int n) {
    // 基本情况
    if (n <= 1) {
        return n;
    }

    // 如果结果已经计算过了，直接返回
    if (memo[n] != -1) {
        return memo[n];
    }

    // 递归计算并存储结果
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n;
    std::cout << "Enter a positive integer: ";
    std::cin >> n;

    if (n < 0) {
        std::cout << "Please enter a non-negative integer." << std::endl;
        return 1;
    }

    // 初始化记忆化数组
    memo.resize(n + 1, -1);

    std::cout << "Fibonacci number at position " << n << " is " << fibonacci(n) << std::endl;
    return 0;
}

解释

1. 记忆化数组：使用 std::vector<int> memo 来存储已计算的斐波那契数。初始化为 -1 表示这些值尚未计算。

2. fibonacci 函数：

   • 检查 n 是否小于等于 1，如果是，直接返回 n。
   • 检查 memo 数组中是否已有计算结果，如果有，直接返回该结果。
   • 否则，计算 fibonacci(n - 1) 和 fibonacci(n - 2)，将结果存储在 memo[n] 中，并返回这个值。

3. 主函数：

   • 从用户输入中读取非负整数 n。
   • 初始化记忆化数组的大小，并将所有元素设为 -1。
   • 调用 fibonacci 函数计算并输出第 n 个斐波那契数。

记忆化递归将时间复杂度降低到 O(n)，因为每个子问题只计算一次