直接递归算斐波那契在C++中很慢是因为重复计算子问题，时间复杂度达O(2^n)；动态规划通过缓存中间结果（如用vector自底向上计算）将时间复杂度降至O(n)。
为什么直接递归算斐波那契在 C++ 里很慢
因为 fib(n) 会重复计算大量子问题，比如 fib(5) 调用 fib(3) 两次，fib(4) 调用 fib(3) 又两次——随着 n 增大，时间复杂度飙升到 O(2^n)，不是卡顿，是根本等不到结果。
动态规划的核心就是「算过一次就记下来，下次直接拿」。C++ 里最自然的做法是用数组或 std::vector 缓存中间结果。
用 vector 实现自底向上 DP（推荐初学）
从 fib(0) 和 fib(1) 开始，一步步推到 fib(n)，空间换时间，时间复杂度降到 O(n)，空间也是 O(n)：
int fib(int n) {
if (n <= 1) return n;
std::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];
}
- 注意
dp大小是n + 1，否则访问dp[n]越界 - 输入
n = 0或1必须提前返回，不然vector构造会出错 - 如果只求值不存路径，可以用两个变量滚动更新，把空间压到
O(1)
用 memoization 改写递归（保留原逻辑）
如果你非得用递归结构（比如题目强制要求「递归接口」），那就加个记忆化表，通常用 std::unordered_map 或 vector（索引明确时更高效）：
立即学习“C++免费学习笔记（深入）”；
int fib(int n, std::vector& memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib(n-1, memo) + fib(n-2, memo); return memo[n]; } int fib(int n) { std::vector memo(n + 1, -1); return fib(n, memo); }
-
memo初始化为-1表示未计算，避免和合法的0混淆 - 传引用
std::vector，否则每次递归都拷贝，反而更慢& - 若
n很大（比如 > 10⁵），vector 索引可能越界，这时改用std::unordered_map更安全，但常数更大
溢出和类型陷阱必须手动处理
C++ 不做运行时整数溢出检查。int 在大多数平台撑不过 fib(47) 就溢出，输出负数或错误值，但编译器不会报错。
- 用
long long可延缓到fib(93)左右 - 真要算更大的，得上
boost::multiprecision或手写大数，但那就超出 DP 优化范畴了 - 函数参数和返回值类型要统一，别一个用
int、一个用size_t，n = -1传进来会变成极大正数
DP 本身不难，难的是边界判断、类型选择和内存管理——这些地方一松懈，程序就 quietly 错了。
