结论：用unordered_map或数组缓存重复子问题结果是最常用有效的Memoization实现方式；普通递归因重叠子问题导致O(2^n)时间复杂度，加缓存后降为O(n)，但栈深度不变。
直接说结论：用 unordered_map 或数组做缓存，把重复子问题的结果“记下来”，下次直接返回——这是 C++ 里最常用、最有效的 Memoization 实现方式。
为什么普通递归会慢到卡死？
比如 fib(40)，原始递归调用次数超过 2 亿次，因为 fib(35)、fib(30) 这类子问题被反复计算十几甚至上百遍。这不是代码写得不好，而是递归树天然存在大量重叠子问题。
关键点在于：子问题由参数唯一确定（如 n），且解不随调用路径变化——这正是缓存能生效的前提。
- 不加缓存时，时间复杂度是
O(2^n)，fib(50)就明显卡顿 - 加了缓存后，每个
n最多算一次，变成O(n) - 栈深度仍是
O(n)，和迭代不同，Memoization 不减少递归层数，只消灭重复工作
用 unordered_map 缓存：适合参数范围不确定的场景
当输入参数可能很大（比如 n 达到 1e6）、或不是连续整数（比如是坐标对 (x, y)、状态压缩的 bitset），数组就不适用了，unordered_map 是更灵活的选择。
立即学习“C++免费学习笔记（深入）”；
注意必须用 static 声明缓存变量，否则每次递归调用都会新建一个空表：
long long fib(int n) {
static std::unordered_map<int, long long> memo;
if (n <= 1) return n;
if (memo.find(n) != memo.end()) return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n;
}
- 别用
memo[n]直接访问——这会自动插入n:0，干扰判断逻辑 - 用
memo.count(n)或memo.find(n) != memo.end()判断是否存在 - 如果函数会被多线程调用，这个版本不安全；单线程下没问题
用数组缓存：快、简单、但要求参数可索引
当参数是小范围非负整数（比如 n ≤ 1000），用 std::vector 或原生数组效率更高，内存局部性好，无哈希开销。
初始化必须显式设为无效值（如 -1），不能依赖默认构造：
long long fib(int n, std::vector<long long>& 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;
}
- 调用前要确保
memo大小足够：std::vector<long long> memo(n+1, -1) - 别传值传递
memo，否则每次递归都拷贝一份，缓存失效 - 如果函数需重入（比如多个独立计算），缓存应作为参数传入，而非静态变量
容易被忽略的三个细节
很多人照着模板写完发现还是慢，或者结果错，往往栽在这几点上：
- 缓存键没覆盖全部影响结果的参数——比如二维 DP 函数
dfs(x, y)只缓存了x，漏了y - 边界条件写错，导致某次递归没进缓存分支，后续所有依赖它的计算全乱
- 用
int当缓存值类型，但实际结果溢出（如fib(50)超过 2e9），应匹配返回类型用long long
缓存不是加个变量就完事，它必须和递归逻辑严丝合缝——少查一次、多算一次，性能和正确性都会出问题。
