直接递归超时因重复计算子问题，加std::map缓存将时间复杂度从O(2^n)降至O(n)；但需正确初始化（避免局部定义或全局冲突），推荐传参或封装类中，并优先用std::unordered_map优化查找。
为什么直接递归会超时，而加个 std::map 就能救回来？
因为重复子问题太多。比如算 fib(40) 时，fib(38) 被算至少两次，fib(35) 可能被算几十次——时间复杂度从指数级 O(2^n) 掉到线性 O(n)。但 std::map 不是白用的：每次查找/插入都是 O(log n)，如果键类型简单（如 int），换成 std::unordered_map 更快（平均 O(1)）。
std::map 缓存怎么初始化和查写才不翻车？
别在递归函数里定义局部 std::map，否则每次调用都清空；也别盲目用全局变量，多线程或多次调用会冲突。稳妥做法是把缓存作为函数参数传入，或封装进类里：
int fib(int n, std::unordered_map<int, int>& memo) {
if (n <= 1) return n;
if (memo.find(n) != memo.end()) return memo[n]; // 已算过
memo[n] = fib(n-1, memo) + fib(n-2, memo); // 计算并缓存
return memo[n;
}
- 用
memo.find(n) != memo.end()比memo.count(n)稍快（避免二次哈希） - 键类型必须支持比较（
std::map）或哈希（std::unordered_map），自定义结构体得重载operator<或提供哈希特化 - 如果只读不改缓存，传
const std::unordered_map<int, int>&会编译失败——得用指针或非 const 引用
记忆化搜索 vs 普通动态规划：什么时候该选 std::map？
当状态空间稀疏或不可预估时。dp[i][j] 数组要求 i、j 范围明确且不大；但像“路径和等于 target 的所有二叉树路径”这类题，状态是 (node_ptr, sum)，没法开数组，std::map<std::pair<TreeNode*, int>, bool> 就很自然。不过要注意：
-
std::pair作键时，两个成员都得可比较（TreeNode*比较的是地址，没问题） - 若键含浮点数，慎用——精度误差会导致查不到缓存；改用
round(x * 1000)转整数再存 - 缓存太大时（比如百万级键值对），考虑定期清理或换 LRU cache（标准库没现成的，得手写）
常见报错和调试技巧
最常遇到的是 std::bad_alloc（内存爆了）或无限递归（缓存没生效）。快速验证缓存是否起作用：
立即学习“C++免费学习笔记（深入）”；
- 在查缓存前加计数器：
static int hit = 0, miss = 0;，命中时++hit，未命中时++miss，最后打印比例 - 错误信息
error: use of deleted function 'std::unordered_map<...>::unordered_map(const std::unordered_map<...>&)'：说明你试图拷贝一个含不可拷贝键（如std::unique_ptr）的 map，改用移动语义或换键类型 - 递归深度过大导致栈溢出？不是缓存的问题，是没加边界检查或状态设计有环——先确保原递归逻辑正确，再加缓存
缓存本身不改变算法逻辑，只加速；如果结果错了，一定是原始递归分支漏了条件，或者缓存键没覆盖所有影响因素（比如忘了把某个参数塞进 key 里）。
