C++斐波那契数列问题是用什么算法

在C++中，计算斐波那契数列通常使用动态规划算法。这是因为斐波那契数列的特点是每个数字都是前两个数字之和，这种递推性质非常适合用数组或矩阵的形式来存储中间结果，避免了重复计算。常见的有两种方法：

1. **迭代法**：通过循环结构，逐步计算并更新每个斐波那契数值，直到达到所需的项数。这种方法空间复杂度较低，只需要常数级别的额外空间。

int fibonacci(int n) {
    if (n <= 1) return n;
    int fib[n + 1];
    fib[0] = fib[1] = 1;
    for (int i = 2; i < n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

2. **递归法**：虽然理论上可以用递归直接求解，但由于递归会重复计算很多次相同的值，效率较低。在实际编程中，可以采用"记忆化搜索"（Memoization）技术，将已计算的结果保存起来，避免重复。

#include <unordered_map>

int fibonacci(int n, std::unordered_map<int, int>& memo) {
    if (memo.find(n) != memo.end()) return memo[n];
    if (n <= 1) return n;
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

// 使用时先初始化 memo
std::unordered_map<int, int> memo;
fibonacci(n, memo);