记忆化搜索（Memoization）是自顶向下的动态规划实现方式，用递归 + 缓存代替递推，代码更直观、状态空间按需计算，是面试中快速写出 DP 的利器。
一、自顶向下 vs 自底向上
Mermaid · 渲染中（下方为源码）
graph TD A[递归] --> B[加缓存=记忆化] B --> C[避免重复子问题]
| 维度 | 记忆化搜索（Top-Down） | 递推（Bottom-Up） |
|---|---|---|
| 方向 | 从目标状态向子问题展开 | 从基础状态向目标推进 |
| 实现 | 递归 + 缓存 | 循环 + 数组 |
| 状态计算 | 按需（只算用到的） | 全量（可能算多余的） |
| 代码直觉 | 更接近数学定义 | 需要确定遍历顺序 |
| 栈溢出风险 | 有（递归深度） | 无 |
二、基本模板
Map<String, Integer> memo = new HashMap<>();
// 或 int[][] memo（状态是整数时更高效）
int solve(int state1, int state2) {
// 1. 边界
if (baseCase) return baseValue;
// 2. 查缓存
String key = state1 + "," + state2;
if (memo.containsKey(key)) return memo.get(key);
// 3. 递归计算
int result = 0;
for (choice : choices) {
result = Math.max(result, solve(nextState) + gain);
}
// 4. 存缓存
memo.put(key, result);
return result;
}