用记搜暴打所有 DP 题?!（1）（线性 DP 、区间 DP 、环形 DP ）

mediocre_ · 2025-07-05 20:56:06 · 算法·理论

真人真事，本人因为上 DP 的课时候没有认真听，自己研究出了一套记搜无敌的方法。

本两篇文章将讲解记搜如何对线性 DP 、区间 DP 、环形 DP 、状压 DP 进行降维打击（你问我为什么没有树形 DP 和数位 DP ？前者是因为已经是记搜了，后者是我还不会（滑稽））。

此章内容难度在黄~绿之间，适合 MnZn ，大佬可以不看啦。

下一章（状压篇）内容难度在绿~蓝之间，已写好。

进入正题。

为什么我喜欢记搜呢？看完这篇文章您应该就有深刻的体会了。

记搜三部曲：爆搜（但是递归形式）-> 舍去不必要的数组（例如标记数组，设不去可以状压，但目前没学，下一篇会讲）-> 保留有关变量记忆化

1.线性 dp

1.1 p1006 传纸条

直接根据题目写出爆搜代码：

int dfs(int sx, int sy, int dx, int dy) {
    if (sx == dx && sy == dy) return INT_MIN;
    if (sx > n || sy > n || dx < 1 || dy < 1) return INT_MIN;
    if (sx == n && sy == n && dx == 1 && dy == 1) return 0;
    int res1 = dfs(sx + 1, sy, dx - 1, dy);
    int res2 = dfs(sx + 1, sy, dx, dy - 1);
    int res3 = dfs(sx, sy + 1, dx - 1, dy);
    int res4 = dfs(sx, sy + 1, dx, dy - 1);
    return max({res1, res2, res3, res4}) + a[sx][sy] + a[dx][dy];
}

这里已经完成了三部曲的前两部了：写出爆搜且没有辅助数组。

显然这里的 sx , sy , dx , dy 都为有关状态，故可以直接加上记忆化：

int dfs(int sx, int sy, int dx, int dy) {
    if (sx == dx && sy == dy) return INT_MIN;
    if (sx > n || sy > n || dx < 1 || dy < 1) return INT_MIN;
    if (sx == n && sy == n && dx == 1 && dy == 1) return 0;
    if (dp[sx][sy][dx][dy]) return dp[sx][sy][dx][dy];
    int res1 = dfs(sx + 1, sy, dx - 1, dy);
    int res2 = dfs(sx + 1, sy, dx, dy - 1);
    int res3 = dfs(sx, sy + 1, dx - 1, dy);
    int res4 = dfs(sx, sy + 1, dx, dy - 1);
    return dp[sx][sy][dx][dy] = max({res1, res2, res3, res4}) + a[sx][sy] + a[dx][dy];
}

为什么当 dp 数组的这一状态有了数值之后就可以直接返回呢？

其实是显然，这道题中的每个状态的 dp 方案其实答案是唯一的，不用继续搜下去。

这样使得这道题的时间复杂度为从 O(4^n) 变到了 O(n^4) ,是一个质的飞跃！

1.2 p7074 [CSP-J2020]方格取数

这道题写出不添加辅助数组的搜索还是有点难的。

应为这道题的操作是向上、向下或向右走一格，就是因为多了这向上走一格的操作就把题目从橙->绿。

实际上，在爆搜中，我们可以多添加一个变量来记录上一次的操作，我们且称这个变量叫做 z 。

当 z 等于 0 时，上一步就是向右走，当前的答案就是向下走与向上走与向右走的最大值加上当前的这一格的值。

而当 z 等于 1 时，上一步就是向下走，如果这一步向上走的话那就走过重复的路了，不可行，故当前的答案就是向下走与向右走的最大值加上当前这一格的值；同理 z 等于 2 时当前答案就是向上走与向右走的最大值加上当前这一格的值。

故我们可以写出如下爆搜代码：

int dfs(int x, int y, int z) {
    if (x > n || y > m || x < 1 || y < 1) return INT_MIN;
    if (x == n && y == m) return a[n][m];
    if (z == 1) return max(dfs(x + 1, y, 1), dfs(x, y + 1, 0)) + a[x][y];
    if (z == 2) return max(dfs(x - 1, y, 1), dfs(x, y + 1, 0)) + a[x][y];
    return max(dfs(x + 1, y, 1), dfs(x - 1, y, 2), dfs(x, y + 1, 0)) + a[x][y];
}

显然函数中的 x , y , z 是有关变量，故记忆化搜索代码为：

long long dfs(int x, int y, int z) {
    if (x > n || y > m || x < 1) return -INF;
    if (dp[x][y][z] != -INF) return dp[x][y][z];
    if (x == n && y == m) return dp[x][y][z] = a[n][m];
    if (z == 1) return dp[x][y][z] = max(dfs(x + 1, y, 1), dfs(x, y + 1, 0)) + a[x][y];
    if (z == 2) return dp[x][y][z] = max(dfs(x - 1, y, 2), dfs(x, y + 1, 0)) + a[x][y];
    return dp[x][y][z] = max({dfs(x + 1, y, 1), dfs(x - 1, y, 2), dfs(x, y + 1, 0)}) + a[x][y];
}

1.3 小结

作者用了两道线性 dp 的题来引入记忆化搜索是为了让读者更好的理解，在接下来的例题中，作者就不会在写爆搜代码了。

2.区间 dp

2.1 P2858 [USACO06FEB] Treats for the Cows G/S

这道题直接写出来爆搜还是要一点思维的。

我们可以这样写，设置左指针 l 为 1 ，右指针 r 为 n ，每次拿出都去搜索下去看拿出哪里的盘子更好，同时需要一个变量 day 记录是第几天，记忆化后的代码如下:

int dfs(int day, int l, int r) {
    if (r < l) return 0;
    if (dp[l][r]) return dp[l][r];
    return dp[l][r] = max(dfs(day + 1, l + 1, r) + day * a[l], dfs(day + 1, l, r - 1) + day * a[r]);
}

从这道题就可以看出记搜在对于区间dp题目时的做法了：设左右指针，分为两种。

就是像本题一样两个指针向中间压缩
将左右指针都设为一个定值向两边扩展。

2.2 P1775 石子合并（弱化版）

像上一题一样，设左右两个指针向中间压缩，只不过这里需要在内部左右指针的范围内枚举 k ，将函数分成 l 到 k 和 r 到 k 两个区间，直到 l = r 时返回，看 k 在哪个值时最大。

int dfs(int l, int r) {
    if (l == r) return 0;
    if (dp[l][r] != INT_MAX) return dp[l][r];
    for (int k = l; k < r; ++k) 
        dp[l][r] = min(dp[l][r], dfs(l, k) + dfs(k + 1, r) + a[r] - a[l - 1]);
    return dp[l][r];
}

2.3 P1880 [NOI1995] 石子合并

这题与上题的区别是石子是环形的还要求最大值与最小值，实际上与上题做法一样，只不过因为题目是环形，所以将原来的数组复制一遍到后面就可以了，这里直接给出本题的完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n, a[N], dp1[N][N], dp2[N][N];
int dfs1(int l, int r) {
    if (l == r) return 0;
    if (dp1[l][r] != INT_MAX) return dp1[l][r];
    for (int k = l; k < r; ++k) 
        dp1[l][r] = min(dp1[l][r], dfs1(l, k) + dfs1(k + 1, r) + a[r] - a[l - 1]);
    return dp1[l][r];
}
int dfs2(int l, int r) {
    if (l == r) return 0;
    if (dp2[l][r] != INT_MIN) return dp2[l][r];
    for (int k = l; k < r; ++k) 
        dp2[l][r] = max(dp2[l][r], dfs2(l, k) + dfs2(k + 1, r) + a[r] - a[l - 1]);
    return dp2[l][r];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), a[i + n] = a[i];
    for (int i = 2; i <= (n << 1); ++i)
        a[i] += a[i - 1];
    for (int i = 1; i < (n << 1); ++i)
        for (int j = 1; j < (n << 1); ++j)
            dp1[i][j] = INT_MAX, dp2[i][j] = INT_MIN;

    int ans1 = dfs1(1, (n << 1) - 1), ans2 = dfs2(1, (n << 1) - 1); ans2 = 0;
    for (int i = 1; i < n; ++i) ans1 = min(ans1, dp1[i][i + n - 1]);
    for (int i = 1; i < n; ++i) ans2 = max(ans2, dp2[i][i + n - 1]);
    printf("%d\n%d", ans1, ans2);
    return 0;
}

2.4 P1220 关路灯

注意到老张被规定了位置，所以将两个指针都设为老张的位置向左右两边扩展。

注意：若原来老张在左边，而下一步答案要他向右扩展，则他走的距离应该是左指针到扩展后右指针的距离。若在同侧，则是下一步的到现在位置的距离。

此题还需要老张上一步站的位置在左边还是在右边（也就是代码中的 in ）与开着的灯的总功率（也就是代码中的 pos ），在关完一盏灯后，注意将 pos 减去这盏灯的功率，代码如下：

int dfs(int l, int r, int pos, int in) {
    if (!pos || l < 1 || r > n) return 0;
    if (dp[l][r][in] != -1) return dp[l][r][in];
    int ans1 = pos * ((in) ? (u[r + 1] - u[r]) : (u[r + 1] - u[l])) + dfs(l, r + 1, pos - a[u[r + 1]], 1);
    int ans2 = pos * ((in) ? (u[r] - u[l - 1]) : (u[l] - u[l - 1])) + dfs(l - 1, r, pos - a[u[l - 1]], 0);
    if (l == 1) return dp[l][r][in] = ans1;
    if (r == n) return dp[l][r][in] = ans2;
    return dp[l][r][in] = min(ans1, ans2);
}

3.环形 dp

3.1 P1057 [NOIP 2008 普及组] 传球游戏

直接按照题意去爆搜然后直接记忆化，统计向左传的方案数与向右传的方案数，注意边界的处理：

int dfs(int u, int step) {
    if (step == m) return (u == 1);
    if (dp[u][step]) return dp[u][step];
    return dp[u][step] = dfs((u == n) ? 1 : u + 1, step + 1) + dfs((u == 1) ? n : u - 1, step + 1);
}

单独出环形 dp 的题还是太少了，大多数环形 dp 只是区间 dp 的一部分。

4.结语

希望大家在阅读完本篇文章之后可以对记忆化搜索有更深刻的体会。

本篇文章完结撒花~★,°:.☆(￣▽￣)/$:.°★ 。