一、题目概述

题目要求计算斐波那契数列的第 n 项。该数列定义如下：F(0) = 0，F(1) = 1；对于任意 n > 1，满足递推关系 F(n) = F(n-1) + F(n-2)。给定一个整数 n（范围为 0 ≤ n ≤ 30），需返回 F(n) 的值。

示例说明：
当输入 n = 4 时，输出应为 3。
推导过程：F(2) = 1，F(3) = 2，因此 F(4) = F(3) + F(2) = 2 + 1 = 3。

二、解题策略演进：从递归到动态规划优化

斐波那契数列是理解算法优化路径的经典案例，其求解方式体现了“避免重复计算”的核心思想，逐步演化出更高效的实现方法。

1. 基础递归法（直观但性能差）

思路分析：
直接依据数学公式进行递归调用。虽然代码简洁易懂，但由于未保存中间结果，导致大量子问题被重复求解。

代码实现：

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib(n - 1) + fib(n - 2);
    }
};

存在问题：
时间复杂度高达 O(2)，主要源于重复计算。例如，在计算 F(5) 时，F(3) 会被多次调用。当 n 接近 30 时，函数调用次数迅速膨胀至百万级别，效率极低。

2. 记忆化搜索（引入缓存机制）

优化思路：
通过额外存储结构记录已计算的结果，每次递归前先检查是否已存在对应值，若有则直接返回，避免重复运算。

实现方式：
使用长度为 n+1 的数组 memo，初始化为 -1，表示尚未计算。若 memo[n] 不为 -1，则说明已计算过，直接取值即可。

代码展示：

class Solution {
private:
    vector<int> memo;

public:
    int fib(int n) {
        memo.resize(n + 1, -1);
        return dfs(n);
    }

    int dfs(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo[n] != -1) return memo[n];
        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
};

性能提升：
时间复杂度降至 O(n)，每个状态仅计算一次；空间复杂度为 O(n)，用于存储缓存数组与递归栈。

3. 动态规划迭代法（最优解）

设计思想：
将问题转化为自底向上的状态转移过程，利用前两个状态推导当前状态。

• 状态定义： dp[i] 表示第 i 个斐波那契数。
• 转移方程： 当 i ≥ 2 时，dp[i] = dp[i-1] + dp[i-2]。
• 初始条件： dp[0] = 0，dp[1] = 1。

进一步观察发现，当前项仅依赖前两项，无需维护整个数组。可通过三个变量滚动更新实现空间压缩。

优化后代码：

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int a = 0, b = 1, c;
        for (int i = 2; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

优势总结：
- 时间复杂度：O(n)
- 空间复杂度：O(1)，仅使用常数级变量
此方案在时间和空间上均达到最优，适合工程实践中的高频调用场景。

三、方法对比与核心思想提炼

三种解法代表了算法优化的不同阶段：

1. 暴力递归： 思路最自然，但存在严重冗余计算，效率低下。
2. 记忆化递归： 引入缓存打破重复子问题困境，实现时间换空间的初步优化。
3. 动态规划迭代版： 彻底摒弃递归开销，结合滚动变量实现空间压缩，达成时间与空间双优。

尽管题目限制 n 最大为 30，所有方法均可通过测试，但从实际应用角度出发，推荐采用空间优化的动态规划方法作为首选方案。它体现了从“以空间换时间”到“时空双赢”的演进逻辑。

四、延伸思考：面对更大规模输入的优化方向

若 n 极大（如 1e6 量级），上述线性方法仍可能超时。此时可考虑以下高级技术：

• 矩阵快速幂： 利用斐波那契的矩阵表达形式，通过快速幂将时间复杂度降至 O(log n)。
• 通项公式法： 使用 Binet 公式直接计算，但受限于浮点精度，适用于对精度要求不高的场合。

然而，针对当前题目设定（n ≤ 30），动态规划的迭代实现已完全足够且最为稳妥。