记忆化搜索
记忆化搜索(Memoization Search)是带缓存的深度优先搜索:搜索时把已经算过的状态结果存下来,再次遇到相同状态直接返回。它写法上是搜索,效率上等价于动态规划——是理解"搜索 → DP"过渡的最佳途径。
从最朴素的递归说起
求斐波那契数列第 n 项:
long long fib(int n) {
if (n <= 1) return 1;
return fib(n - 1) + fib(n - 2);
}
问题很明显:fib(5) 会递归调用 fib(3) 三次,fib(2) 五次……分支随深度指数膨胀。
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ │ ├─ fib(2)
│ │ └─ fib(1)
│ └─ fib(2) ← 重复
└─ fib(3) ← 重复
├─ fib(2) ← 重复
└─ fib(1)
n = 40 时就要算约 3 亿次,n = 50 直接卡死。
加上记忆
既然 fib(3) 的结果只取决于 3,算一次就够:
long long memo[100];
bool visited[100];
long long fib(int n) {
if (n <= 1) return 1;
if (visited[n]) return memo[n]; // ← 核心:已算过直接返回
visited[n] = true;
return memo[n] = fib(n - 1) + fib(n - 2); // ← 记录
}
复杂度从 O(2^n) 降到 O(n)——每个状态只计算一次。
这里用 visited 而不是判断 memo[n] != 0,是因为结果可能本来就是 0,用 0 当哨兵会误判。如果题目保证结果为正,可以省略 visited。
记忆化搜索的标准模板
int memo[N]; // N 是状态空间大小
bool vis[N];
int dfs(状态参数) {
// 1. 边界:递归出口
if (到达终点) return 初始值;
// 2. 查表:算过就直接用
if (vis[key]) return memo[key];
// 3. 标记 + 递推
vis[key] = true;
int res = 初始值(如 INF / 0);
for (每个转移) {
res = max/min(res, 转移后的值);
}
// 4. 存表 + 返回
return memo[key] = res;
}
这个模板和动态规划的状态转移方程几乎一一对应:dfs(状态) 就是 dp[状态],if (vis) 就是"如果已经计算过",res = max(...) 就是转移方程。
例题:数字三角形
题目:一个数字三角形,从顶端出发,每次可以走到下一层的相邻位置,求到底边的最大路径和。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
朴素搜索
int dfs(int i, int j) {
if (i == n) return 0;
return a[i][j] + max(dfs(i + 1, j), dfs(i + 1, j + 1));
}
复杂度 O(2^n),n = 100 就爆了。
记忆化版本
int memo[105][105];
int dfs(int i, int j) {
if (i == n) return 0;
if (memo[i][j] != -1) return memo[i][j]; // 已算过
return memo[i][j] = a[i][j] + max(dfs(i + 1, j), dfs(i + 1, j + 1));
}
// 调用前初始化
memset(memo, -1, sizeof(memo));
cout << dfs(0, 0);
状态是 (i, j) 两个下标,共 O(n²) 个状态,每个状态 O(1) 转移 → 总复杂度 O(n²)。
例题:带约束的路径计数
题目:在 n×m 网格中从左上走到右下,每步只能向右或向下,且不能经过障碍。求方案数。
const int MOD = 1e9 + 7;
int n, m;
bool blocked[1005][1005];
int memo[1005][1005];
int dfs(int i, int j) {
if (i >= n || j >= m || blocked[i][j]) return 0; // 越界或障碍
if (i == n - 1 && j == m - 1) return 1; // 到达终点
if (memo[i][j] != -1) return memo[i][j]; // 查表
return memo[i][j] = (dfs(i + 1, j) + dfs(i, j + 1)) % MOD;
}
注意这里 dfs(i, j) 只依赖坐标,所以能用二维数组记忆化。如果状态里还带了"已经收集了多少个物品"这种维度,就要把这一维也纳入缓存下标。
什么时候用记忆化搜索
| 情况 | 推荐 |
|---|---|
| 状态转移关系清晰、循环顺序容易确定 | 直接写 DP |
| 转移依赖较复杂、难以确定遍历顺序 | 记忆化搜索 |
| 状态空间稀疏(只有部分状态可达) | 记忆化搜索(只算用到的) |
| 有环依赖 | 记忆化不能用(会死循环) |
记忆化搜索的最大优势是只计算真正需要的状态。动态规划要把整个状态表填满,而记忆化搜索从终态出发,不会碰到无关状态。
与动态规划的关系
两者本质等价:
记忆化搜索(自顶向下) 动态规划(自底向上)
dfs(状态) for (状态按拓扑序)
├ 查表 dp[状态] = 转移(dp[前置状态])
├ 递归子问题
└ 存表返回
能把记忆化搜索改成递推 DP 的前提是:状态的依赖关系无环,且能找到一个遍历顺序,保证计算某个状态时它依赖的状态都已算完。
常见错误
- 用 0 作"未访问"哨兵:如果真实答案可能是 0,会被误判为"没算过"。用
-1或单独的vis数组。 - 状态定义不完整:只用了坐标做 key,忽略了其他影响结果的参数(如剩余容量)。
- 忘记初始化:
memo数组没设成-1,导致所有状态都被当成"已计算"。 - 递归深度过深:n 很大时爆栈,可以改用迭代或手动栈。
- 有环状态空间:如
A → B → A,记忆化会无限递归。
小结
记忆化搜索 = DFS + 缓存。判断能否使用时只需问两个问题:状态能否用少数几个参数唯一标识?状态依赖是否有环?满足条件时,它能用搜索的写法拿到 DP 的效率,是复杂转移问题最实用的解法。