困难C++4 分钟1,303 字

记忆化搜索

记忆化搜索(Memoization Search)是带缓存的深度优先搜索​​:搜索时把已经算过的状态结果存下来,再次遇到相同状态直接返回。它写法上是搜索,效率上等价于动态规划——是理解"搜索 → DP"过渡的最佳途径。

从最朴素的递归说起

求斐波那契数列第 n 项:

cpp
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,算一次就够:

cpp
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。

记忆化搜索的标准模板

cpp
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

朴素搜索

cpp
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 就爆了。

记忆化版本

cpp
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 网格中从左上走到右下,每步只能向右或向下,且不能经过障碍。求方案数。

cpp
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 的效率,是复杂转移问题最实用的解法。

同类知识点