0。斐波那契数列可通过递归、迭代与动态规划实现，递归法直观但时间复杂度达O(2^n)，存在大量重复计算；迭代法从下往上计算，仅用两个变量保存前两项，时间复杂度O(n)，空间复杂度O(1)，效率更高。
斐波那契数列是经典的数学问题，定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（n ≥ 2）。在C++中，可以通过多种方式实现，每种方法在时间与空间效率上有明显差异。下面介绍三种常见解法：递归、迭代与动态规划。
C++递归实现（简单但低效）
最直观的方法是直接按照定义写递归函数：
#includeusing namespace std; int fib_recursive(int n) { if (n <= 1) return n; return fib_recursive(n - 1) + fib_recursive(n - 2); }
int main() { cout << fib_recursive(10); // 输出 55 return 0; }
这种方法代码简洁，但存在大量重复计算。例如计算fib(5)时，fib(3)会被调用多次。时间复杂度为O(2^n)，不适用于较大的n值。
迭代法（高效且节省空间）
通过从下往上计算，避免重复，使用两个变量保存前两项的值：
立即学习“C++免费学习笔记（深入）”；
int fib_iterative(int n) {
if (n <= 1) return n;
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. 记忆化递归：
#includevector memo(1000, -1); // 假设n不超过999 int fib_memo(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib_memo(n - 1) + fib_memo(n - 2); return memo[n]; }
通过缓存已计算结果，避免重复调用，时间复杂度降为O(n)，空间复杂度为O(n)。
2. 自底向上的DP数组：
int fib_dp(int n) {
if (n <= 1) return n;
vector dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
这种方式逻辑清晰，适合理解动态规划思想，但空间占用比迭代法高。
基本上就这些。对于小规模计算，递归便于理解；追求效率时，推荐使用迭代法；学习算法思想时，动态规划帮助建立优化思维。不复杂但容易忽略的是，递归虽美，性能代价大。
