直接写 fib(n) 递归会超时，因其时间复杂度为 O(2^n)，存在大量重复子问题；例如 fib(5) 中 fib(3) 被调用两次、fib(2) 三次，n 增大时重复急剧增加，fib(45) 已明显卡顿，fib(50) 几乎不可接受。
为什么直接写 fib(n) 递归会超时
裸递归实现 fib(n) 看似简洁，但时间复杂度是 O(2^n)。因为每个 fib(n) 都会重复计算 fib(n-2)、fib(n-3) 等大量子问题。比如算 fib(5) 时，fib(3) 被调用了两次，fib(2) 被调用了三次——越往小的数，重复越严重。
实际运行中，fib(45) 就可能明显卡顿；fib(50) 在多数本地环境已不可接受。
- 不要用
if (n 就直接递归返回 <code>fib(n-1) + fib(n-2) - 即使加了
int返回类型，n > 46时还会整数溢出（int最大约 21 亿） - 若需大数，得换
long long或高精度库，但性能问题不解决，换类型也没用
怎么加记忆化让递归变快
记忆化递归（Memoization）本质是「递归 + 缓存」：用数组或哈希表存下已算过的 fib(i)，下次直接取。
最常用的是用 vector<long long></long> 初始化为 -1，下标即 n 值：
立即学习“C++免费学习笔记（深入）”；
vector<long long> memo(n + 1, -1);
long long fib(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}- 必须初始化为非法值（如 -1），不能用 0——因为
fib(0) == 0是合法结果 - 空间复杂度升为
O(n)，但时间降到O(n) - 注意
memo要传引用或设为全局/类成员，否则每次递归都新建，缓存失效
动态规划怎么写更安全高效
自底向上 DP 省去递归调用栈，也避免深递归导致的栈溢出（比如 n = 100000 时递归必崩，DP 循环却很稳）。
核心是只保留最近两个状态，不用整个数组：
long long fib(int n) {
if (n <= 1) return n;
long long a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
long long c = a + b;
a = b;
b = c;
}
return b;
}- 变量名用
a/b比prev1/prev2更轻量，也更符合 C++ 习惯 - 循环从
i = 2开始，对应算fib(2)，边界清晰 - 如果要返回前
n项，才需要开vector存全部；单求第n项，滚动变量足够
什么时候该选哪种写法
递归写法只适合教学演示或 n 的极小规模；记忆化递归适合逻辑天然递归、且子问题有重叠的场景（比如带限制的路径计数）；而斐波那契这种线性依赖关系，DP 迭代是默认首选。
容易被忽略的一点：n 为负数时，所有上述实现都未处理——C++ 标准没定义负索引斐波那契，若业务需要扩展（如用 fib(-n) = (-1)^(n+1) * fib(n)），必须显式判断并分支实现，不能靠递归自动收敛。
