今天我们聊聊记忆化搜索（Memoization Search）喵！
用一句话来说记忆化搜索就是：“好记性不如烂笔头，算过一次绝不来第二回！”
记忆化搜索：精明打工人的“记仇小账本” 
1. 把它想象成“高考试卷判卷人”的故事
想象一下，你是一位正在批改大量数学试卷的阅卷老师。这道题极其复杂，算一次要耗费半小时。
- 没有记忆化的程序：
改到小明的试卷，中间有一个超复杂的步骤叫 f(5)，你吭哧吭哧算出来等于 100（本人瞎写的）。但你改到小红的试卷，发现里面也有一个 f(5)。你把之前的忘干净了，又吭哧吭哧算了一遍得出 100。结果小刚……的试卷全都有 f(5)，你一共算了 50 次同样的步骤，人直接累瘫了
（这就会导致 TLE）。 - 开启了记忆化搜索：这次你桌上放了一个本子（数组）。
你改到小明时，你要算 f(5)。一看本上是空的，于是你第一次算出了100，并立刻把它写在本上：f(5) = 100。改到小红时，又要算 f(5)。你不急着算，而是往本上一瞅——上面写着 100 呢！你直接对照试卷查看对错，耗时：0.0001秒（也是本人瞎写的，只用知道快了很多就好）！
这就是记忆化搜索：在程序往下运行时，每算出一个状态的答案，就把它存进数组里。下次再遇到相同的状态，直接查表拿答案，绝不重复计算！
2. 记忆化搜索的优缺点喵
- 优点： 它的运行速度快，但写起来却和普通的 DFS 一样“特别简单直观”！你“只要”在 DFS 的基础上加个本子就行了。
- 缺点： 因为要开一个数组来记数，所以也会消耗一定的空间。
3. 那它 C++ 代码长什么样？
记忆化搜索的核心公式就是“两步走”：
- 进门先查账（如果算过，直接返回）。
- 出门必记账（算出了结果，先存进账本再 return）。
int ans[210][210][210];
int dfs(int x, int y, int z) {
if (ans[x][y][z] != 0) {
return ans[x][y][z];
}
if (x >= 1 && y >= 1) ans[x][y][z] = max(ans[x][y][z], dfs(x-1, y-1, z) + red[x] * yel[y]);
if (x >= 1 && z >= 1) ans[x][y][z] = max(ans[x][y][z], dfs(x-1, y, z-1) + red[x] * ble[z]);
if (y >= 1 && z >= 1) ans[x][y][z] = max(ans[x][y][z], dfs(x, y-1, z-1) + ble[z] * yel[y]);
return ans[x][y][z];
}