递归慢主因是重复计算子问题，记忆化通过缓存有限参数组合的结果来消除指数级冗余；关键前提是参数组合有限且纯函数式，需正确初始化、查询与存储缓存，避免漏return或误用容器。
为什么递归慢？不是递归本身，是重复算
记忆化搜索不是给递归“加个缓存”就完事，而是砍掉指数级重复子问题。比如 fib(40) 普通递归调用超 2 亿次，但不同输入最多就 41 种——其余全是白算。
关键判断：只要递归函数的参数组合有限、且相同参数总会返回相同结果，就适合加记忆化。
- 常见场景：
dfs(i, j)在二维网格路径计数、knapsack(pos, weight)背包、字符串区间dp(l, r) - 不能乱加：如果参数里有指针、全局状态、随机数、时间戳，缓存会失效或出错
- 性能影响：空间换时间，最坏多占 O(状态数) 内存；但避免栈爆炸比盲目剪枝更可靠
怎么写记忆化？三步封住重复入口
核心动作就三件事：声明缓存、查缓存、存结果。别绕弯，C++ 里最稳的是用 std::map 或数组，别一上来就上 unordered_map ——哈希冲突在小规模状态里反而拖慢。
- 用数组最快：如果参数范围明确（如
i∈ [0,100]，j∈ [0,100]），直接int memo[101][101]，初始化为一个非法值（如-1） - 用
std::map更安全：参数类型复杂时，比如map<pair>, int></pair>存(i,j)→ 结果，查前先if (memo.count({i,j})) return memo[{i,j}] - 别在递归入口外初始化缓存：每次调用都清空，否则多组测试用例会串数据；推荐局部静态变量或传参进去
示例（斐波那契）：
立即学习“C++免费学习笔记（深入）”；
int fib(int n, vector<int>& memo) {
if (n < 2) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}
// 调用前：vector<int> memo(41, -1);
递归爆栈？不是深度问题，是没剪枝+没优化返回路径
记忆化本身不减少递归深度，只减少调用次数。但很多人加了记忆化还爆栈，是因为忘了两个硬约束：
- 递归深度仍由最深那条路径决定，比如树高 1e5 的链式结构，
stack overflow照样发生 - 返回值没及时传播：缓存命中后必须立刻
return，别再往下走；漏写return是高频 bug - 注意编译器优化：
-O2下某些尾递归可能被转成循环，但 C++ 标准不保证，别依赖
错误写法（缓存命中却继续执行）：
if (memo[n] != -1) memo[n]; // ❌ 少了 return return fib(n-1, memo) + fib(n-2, memo); // 这行永远会跑
vector 和 array 哪个快？看维度和初始化方式
单维小范围（≤1e4）用 vector 安全；多维或确定大小，优先用原生 array 或 C 风格数组。别信“vector 更现代”，它每次构造带零初始化开销，而 int memo[1000][1000] 在栈上分配快得多。
-
vector<vector>></vector>：每层 new 分配，缓存不友好，访问慢；仅当某维长度不固定时才用 -
int memo[1000][1000]：栈上连续内存，CPU 预取友好；但总大小别超几 MB，否则栈溢出 - 真正大状态（如 1e6 个状态）：改用
static vector<int> memo</int>，只初始化一次，但注意多线程不安全
容易被忽略的一点：所有缓存变量必须初始化为无效值（如 -1、INT_MIN），不能靠默认构造——vector<int>(N)</int> 初始化为 0，而 0 可能是合法答案。
