01 斐波那契数列的基本原理与定义
在深入C++实现前，需要先掌握斐波那契数列的基本定义，它以
状态转移方程是实现中的核心，是把复杂问题分解为简单子问题并重用结果的关键。理解这一点有助于快速区分递归解法与动态规划解法之间的差异。
在实际编程中，直接用递归实现会产生指数级时间复杂度，因为大量的重复子问题被重复计算。这一特性使简单递归在n较大时效率极低，但它的直观性和易理解性仍然适合作为教学起点，随后再引入记忆化和动态规划来提升性能。
int fib(int n) {if (n < 2) return n;return fib(n-1) + fib(n-2);
}要点总结：递归实现的直观性与效率瓶颈并存，理解它为后续优化提供了清晰的对比基线。
02 递归实现的斐波那契数列
01 简单递归实现的要点
简单递归直接按照定义展开，代码简洁，阅读性高，但时间复杂度为 O(2^n)，当 n 较大时会出现严重的性能瓶颈。此实现的优点在于实现快速上手，缺点在于大量重复子问题导致计算冗余。
另外，递归调用的深度也会影响调用栈使用，在 n 较大时可能触发栈溢出等问题，因此通常只在教学或极小规模的场景使用。
int fib(int n) {if (n < 2) return n;return fib(n-1) + fib(n-2);
}简要结论：简单递归易理解，但在实际工程中通常需要通过优化避免重复计算。
02 递归实现中的性能瓶颈与优化方向
递归实现的主要瓶颈来自于重复子问题的多次计算，因此一个常见的优化方向是<强>记忆化，把已经计算的结果缓存起来，避免重复工作。
在优化方向的选择上，有两条主线：一是自顶向下的记忆化递归，二是<强>自底向上的动态规划。两者都等效地避免了重复计算，但在实现风格和空间/时间权衡方面存在差异。
03 记忆化递归与动态规划对比
01 记忆化递归（自顶向下）
记忆化递归使用一个<缓存结构（如哈希表或数组）来存放已计算的子问题结果，避免重复计算的同时保持递归的直观性。通过这种方式，时间复杂度降至 O(n)，空间复杂度通常为 O(n)，取决于缓存大小和递归栈深度。
典型实现中，先检查缓存中是否有 F(n) 的值，如无则递归计算并将结果存入缓存，最终返回缓存中的结果。
#include <unordered_map>
int fibMemo(int n, std::unordered_map<int,int>& memo) {if (n < 2) return n;if (memo.count(n)) return memo[n];memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);return memo[n];
}int fibTopDown(int n) {std::unordered_map<int,int> memo;return fibMemo(n, memo);
}应用记忆化的核心思想是：避免重复计算，在实现层面提升了算法效率，同时保持了代码的易读性。
02 自底向上的动态规划
自底向上动态规划通过<强>迭代计算，从最小子问题逐步推导出目标值，通常不需要进行大量的递归调用，因此在栈空间方面更加稳健。两种常见实现方式分别对应<强>数组/向量存储和滚动变量的优化。
第一种是使用一个数组来保存中间结果，时间复杂度为 O(n)，空间复杂度为 O(n)；第二种为滚动变量版本，通过仅保留最后两个值，将空间复杂度降为 O(1)，而时间复杂度仍然保持为 O(n)。
#include <vector>
int fibBottomUp(int n) {if (n < 2) return n;std::vector<int> 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];
}// 空间优化：只保留最近的两个值
int fibBottomUpOpt(int n) {if (n < 2) return n;int a = 0, b = 1;for (int i = 2; i <= n; ++i) {int c = a + b;a = b;b = c;}return b;
}结论与对比：记忆化递归适合保留递归思路，动态规划（自底向上）在性能与可控性上更优，两者都可将复杂度从指数级降到线性级别，且后者通常更易进行资源约束优化。
