记忆化搜索

记忆化递归 = 用搜索的方式写 DP。递归天然表达「状态转移」，再加上一个 dp 数组记录算过的答案，避免重复计算，就是记忆化。

它比递推 DP 好在不用纠结拓扑序，状态怎么想得顺就怎么写；坏处是有递归栈开销，某些题目会被卡。

P1044 栈

P1044 [NOIP 2003 普及组] 栈 - 洛谷

这道题还有一个变种，是我一开始学栈的时候就出现的，同源但不同做法。看到 dfs 的时候我惊讶于这道题还能用这么简洁的方式，着实震惊。

状态设计：x 是已经入过栈的数字个数，y 是当前栈里有多少个。

1
2
3
4
5
6
7
8
9
10
11
12
int n;
ll dp[20][20];

ll dfs(int x, int y) {
    if (x == n && y == 0) return 1;      // 所有数字已输出，找到一种合法方案
    if (dp[x][y] != -1) return dp[x][y];

    ll ans = 0;
    if (x < n) ans += dfs(x + 1, y + 1); // 还有数字没进栈
    if (y > 0) ans += dfs(x, y - 1);     // 栈里还有数字没出
    return dp[x][y] = ans;
}

P1028 数的计算

P1028 [NOIP 2001 普及组] 数的计算 - 洛谷

搞清楚：每个数字后面加的数字最多是 n/2，然后 dfs 即可。短小精悍。

1
2
3
4
5
6
7
8
ll dp[1005];

ll dfs(int n) {
    if (dp[n] != 0) return dp[n];
    ll ans = 1;                          // 就自己一个数
    for (int i = 1; i <= n / 2; i++) ans += dfs(i);
    return dp[n] = ans;                  // 别忘了保存结果
}

P1255 数楼梯 与 P2437 蜜蜂路线

P1255 数楼梯 - 洛谷
P2437 蜜蜂路线 - 洛谷

这两道是举一反三的绝佳组合。直接上记忆化递归会超时——因为数值范围远超 long long，不仅会失策，而且其实可以精简 dp，不需要那么多次递归。这时候高精度加法就派上用场了（又复习了一遍）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> add(vector<int>& a, vector<int>& b) {
    int t = 0; vector<int> c;
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10); t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}

int main() {
    int n; cin >> n;
    if (n <= 2) { cout << n << endl; return 0; }

    vector<int> f1 = {1}, f2 = {2}, f3;
    for (int i = 3; i <= n; i++) {       // 斐波那契式递推，滚动数组
        f3 = add(f1, f2);
        f1 = f2; f2 = f3;
    }
    for (int i = f2.size() - 1; i >= 0; i--) cout << f2[i];
    cout << endl;
    return 0;
}

过河卒：DP 与记忆化的两种写法

P1002 [NOIP 2002 普及组] 过河卒 - 洛谷

马和它可能跳到的 8 个点都不能走（注意不止八个点，还有马自己）。递推版状态：dp[i][j] 表示到达 (i,j) 的方案数。

其实用记忆化递归也可以，只要别忘了记忆化：

1
2
3
4
5
6
7
8
9
10
ll dfs(int x, int y) {
    if (x == 0 && y == 0) return 1;
    if (vis[x][y]) return 0;             // vis：预处理马能到达的障碍点
    if (dp[x][y] != -1) return dp[x][y];

    ll ans = 0;
    if (x > 0) ans += dfs(x - 1, y);
    if (y > 0) ans += dfs(x, y - 1);
    return ans;
}

个人觉得递归更好理解，只是需要掌握底层逻辑，不然容易晕。

总结

  • 记忆化递归适合状态转移好想、递推顺序难排的题目。
  • dp 数组记得初始化为 -1，用 0 容易和「没算过」混淆（但像 P1028 这种答案必为正数时，用 0 表示没算过也行）。
  • 数值可能爆 long long 时，要提前想到高精度。