结论：用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 是更灵活的选择。
注意必须用 static 声明缓存变量，否则每次递归调用都会新建一个空表：
long long fib(int n) {
static std::unordered_map<int long> memo;
if (n
<ul>
<li>别用 <code>memo[n]</code> 直接访问——这会自动插入 <code>n:0</code>，干扰判断逻辑</li>
<li>用 <code>memo.count(n)</code> 或 <code>memo.find(n) != memo.end()</code> 判断是否存在</li>
<li>如果函数会被多线程调用，这个版本不安全；单线程下没问题</li>
</ul>
<h3>用数组缓存：快、简单、但要求参数可索引</h3>
<p>当参数是小范围非负整数（比如 <code>n ≤ 1000</code>），用 <code>std::vector</code> 或原生数组效率更高，内存局部性好，无哈希开销。</p>
<p>初始化必须显式设为无效值（如 <code>-1</code>），不能依赖默认构造：</p>
<pre class="brush:php;toolbar:false;">long long fib(int n, std::vector<long long>& memo) {
if (n
<ul>
<li>调用前要确保 <code>memo</code> 大小足够：<code>std::vector<long long> memo(n+1, -1)</long></code>
</li>
<li>别传值传递 <code>memo</code>，否则每次递归都拷贝一份，缓存失效</li>
<li>如果函数需重入（比如多个独立计算），缓存应作为参数传入，而非静态变量</li>
</ul>
<h3>容易被忽略的三个细节</h3>
<p>很多人照着模板写完发现还是慢，或者结果错，往往栽在这几点上：</p>
<ul>
<li>缓存键没覆盖全部影响结果的参数——比如二维 DP 函数 <code>dfs(x, y)</code> 只缓存了 <code>x</code>，漏了 <code>y</code>
</li>
<li>边界条件写错，导致某次递归没进缓存分支，后续所有依赖它的计算全乱</li>
<li>用 <code>int</code> 当缓存值类型，但实际结果溢出（如 <code>fib(50)</code> 超过 2e9），应匹配返回类型用 <code>long long</code>
</li>
</ul>
<p>缓存不是加个变量就完事，它必须和递归逻辑严丝合缝——少查一次、多算一次，性能和正确性都会出问题。</p></long>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
