学术
浅谈棋盘类DP（二）
_Separation WA的一声就哭了 SU @ 2026-1-18 11:38:38

棋盘类 DP （字典序最小路径构造类型）

比较常用的方法有：

最短路 + 字典序最小 ：BFS(分层) / Dijkstra 先算距离，再 分层贪心 选下一步
可达性（DAG）+ 字典序最小 ：先做 can（DP / 反向可达），再按字典序贪心走

关键的思想其实就是：先算 从每个状态到终点是否可行 / 最优代价 ，然后从起点开始，每一步都选字典序最小且不破坏 可行 / 最优 的那条边。

问题描述

给你一个 $n\times n$ 的大写字母网格，从左上角 $(1,1)$ 走到右下角 $(n,n)$ ，每步只能向右或向下。沿途把经过格子的字母依次拼成一个长度为 $2n-1$ 的字符串。

问：所有合法路径里，字典序最小 的那个字符串是什么。 $n\le 3000$ 。

输入样例

4
AACA
BABC
ABDA
AACA

输出样例

AAABACA

解题思路

根据前面棋盘类 DP 的讲解很容易发现：只能 向右 / 向下 ，所以到 $(i,j)$ 的任意路径都固定长度 $i+j-1$ 个格子字符。

定义：

$$dp_{i, j} = \text{从 }(1,1)\text{ 走到 }(i,j)\text{ 的所有路径中，拼出来的字符串字典序最小的那一个} $$

注意：这里的字符串包含 路径上每个格子的字母 ，因此 $dp_{i, j}$ 长度是 $i+j-1$ 。

起点只有一种路径，就可以让 $dp_{1, 1} = grid_{1, 1}$ ，边界为：

第一行只能一直向右： $dp_{1, j} = dp_{1, j - 1} + grid_{1, j}$
第一列只能一直向下： $dp_{i, 1} = dp_{i - 1, 1} + grid_{i, 1}$

转移的话其实就是：到 $(i,j)$ 只能从上面 $(i-1,j)$ 或左边 $(i,j-1)$ 来：

从上来得到的字符串： $dp_{i-1,j} + grid_{i, j}$
从左来得到的字符串： $dp_{i,j-1} + grid_{i, j}$

取字典序更小的：

$$dp_{i, j} = \min_{\text{lex}}\big(dp_{i-1,j},\ dp_{i,j-1}\big) + grid_{i, j} $$

注意：最后加的 $grid_{i, j}$ 相同，所以等价于 先比较 $dp_{i - 1, j}$ 与 $dp_{i, j - 1}$ 哪个更小 。

证明正确性

任意到 $(i,j)$ 的路径，最后一步一定来自上或左：

如果最后来自上，那么整条路径字符串 $=$ （到 $(i-1,j$ ) 的路径字符串） $+$ 当前字符，为了让整条最小，显然要选到 $(i-1,j)$ 的最小字符串，也就是 $dp_{i - 1, j}$ 。
来自左同理。

因此到 $(i,j)$ 的 全局最小字符串 ，一定是 上方最小 与 左方最小 二者中更小的那个再接上当前字符。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
char g[N][N];
string dp[N][N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
    dp[1][1] = string(1, g[1][1]);
    for (int j = 2; j <= n; j++) dp[1][j] = dp[1][j - 1] + g[1][j];
    for (int i = 2; i <= n; i++) dp[i][1] = dp[i - 1][1] + g[i][1];
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            if (dp[i - 1][j] <= dp[i][j - 1]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = dp[i][j - 1];
            dp[i][j].push_back(g[i][j]);
        }
    }
    cout << dp[n][n] << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

分析

当前程序的时间复杂度非常的高， $n \le 3 \times 10^3$ 根本通过不了，具体如下：

$dp_{i, j}$ 的字符串长度约 $i+j$ ，最坏接近 $2n$ 。
每个格子要做一次字符串比较 + 拼接，都是 $O(n)$ 级。

总时间复杂度： $O(n^2 \cdot n)=O(n^3)$ 。

并且空间复杂度也会爆炸，一共有 $n^2$ 个字符串，每个字符串长度 $n$ ，总空间为 $O(n^3)$ 。这也是关于字典许中非常总要的部分，因为拼接的原因。

优化思想

因为朴素 DP 每格存整条字符串（太长、太多） ，那么考虑 每格不存完整字符串，只存父指针 + 用 LCP / 哈希比较字符串 的方式解决，这样就可以把字符串本身的问题处理了。

用 $rank$ + 父指针 的方法，用 $rank$ 来比较字符串大小。

和朴素 DP 的定义还是一样 $dp_{i, j} = \text{从 }(1,1)\text{ 到 }(i,j)\text{ 的最小字典序字符串}$，转移也是 $dp_{i, j} = \min(dp_{i - 1, j},, dp_{i, j - 1}) + g_{i, j}$ 。

关键点在于：不存 $dp_{i, j}$ 字符串，存它的排名。

让 $rank_{i, j} = dp_{i, j}\ \text{在同长度字符串中的字典序排名（越小越好）}$ ，因为在 同一条对角线层（同一步数） 上，字符串 长度相同 ，所以：

比较 $dp_{i - 1, j}$ 和 $dp_{i, j - 1}$ $⟺$ 比较 $rank_{i - 1, j}$ 和 $rank_{i, j - 1}$

这样就不用做 $O(n)$ 的字符串比较了。

接下来考虑如何在一层内给所有格子的 dp-string 建 $rank$ 。

第 $s$ 层定义为所有满足：

i+j=s

的格子 $1-index$ 。这层的 $dp_{i, j}$ 长度固定为 $s-1$ 。

对任意格子 $(i,j)$ $(i+j=s)$ ：

它的 $dp_{i, j}$ 等于 父格子的 dp-string 再加上当前字符 $g_{i, j}$ 。
父格子一定在上一层 $s-1$ 。

所以每个 $dp_{i, j}$ 都能表示成一个二元组：

$$dp_{i, j} \equiv \big(rank_{[parent]},\ g_{i, j}\big) $$

结论：同一层内字典序比较等价于按 $(rank_{parent}, g_{i, j})$ 排序。
因此可以对这一层所有格子收集这些 $pair$ ，排序后压缩成新 $rank$ 。

初始化与转移

dp_{1, 1} = g_{1, 1},\quad rank_{1, 1} = 1

对 $(i,j)$ $(i+j=s)$ ：

若 $i=1$ 只能从左来
若 $j=1$ 只能从上来
否则选择 $rank$ 更小的那个父亲：
$$parent(i,j)= \begin{cases} (i-1,j), & rank_{i - 1, j} < rank_{i, j - 1} \\ (i,j-1), & \text{否则} \end{cases} $$
（相等随便选一个，不影响字符串本身）

然后把该格子的签名记为：

sig(i,j) = (rank_{parent(i,j)},\ g_{i, j})

每层结束后：对本层所有 $sig$ 排序压到 $rank$ ，按 $rank_{parent}$ 先、 $g_{i, j}$ 后排序，遇到新的 $pair$ 就 $rank+1$ 。

答案：最终字符串

通过储存的 $parent$ 指针（从上来还是从左来）。
从 $(n,n)$ 沿 $parent$ 回溯到 $(1,1)$ 收集字符，最后反转即可得到 $dp_{n, n}$ 。

时间复杂度分析

每层（对角线）最多 $O(n)$ 个格子。
对每层做一次排序： $O(n\log n)$ 。
总层数 $2n-1$ 。
总时间复杂度 $O(n^2 \log n)$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Node {
    int pr; char c; int i, j;
    bool operator<(Node const& other) const {
        if (pr != other.pr) return pr < other.pr;
        return c < other.c;
    }
};
int n, rk[N][N];
char g[N][N], par[N][N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
    rk[1][1] = 1;
    for (int s = 3; s <= 2 * n; s++) {
        int il = max(1, s - n);
        int ir = min(n, s - 1);
        vector<Node> sig;
        for (int i = il; i <= ir; i++) {
            int j = s - i;
            int pi, pj;
            if (i == 1) { // 只能从左
                pi = i; pj = j - 1;
                par[i][j] = 1;
            } else if (j == 1) { // 只能从上
                pi = i - 1; pj = j;
                par[i][j] = 0;
            } else {
                // 选 rank 更小的父亲
                if (rk[i - 1][j] < rk[i][j - 1]) {
                    pi = i - 1; pj = j;
                    par[i][j] = 0;
                } else {
                    pi = i; pj = j - 1;
                    par[i][j] = 1;
                }
            }

            sig.push_back({rk[pi][pj], g[i][j], i, j});
        }
        sort(sig.begin(), sig.end());
        // 压缩 rank
        int cur = 0;
        int lastPr = -1; char lastC = 0;
        for (auto &nd : sig) {
            if (nd.pr != lastPr || nd.c != lastC) {
                cur++;
                lastPr = nd.pr;
                lastC = nd.c;
            }
            rk[nd.i][nd.j] = cur;
        }
    }
    // 还原答案字符串
    string Ans;
    int i = n, j = n;
    while (!(i == 1 && j == 1)) {
        Ans.push_back(g[i][j]);
        if (par[i][j] == 0) i--;
        else j--;
    }
    Ans.push_back(g[1][1]);
    reverse(Ans.begin(), Ans.end());
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

继续考虑优化，当前考虑的是 给这一层所有格子排出完整字典序排名（rank） 。

事实上只关心 全局最小字符串 的下一位是什么（一个字符），以及哪些格子能达到这个最小前缀即可。

字典序比较只看最早不同的位置。当你已经确定前缀最小后，下一位想尽量小，就必须在所有 能达到该最小前缀 的位置里，看看下一步能出现的最小字母是多少；选更大的字母一定会让字符串变差。选定 bestChar 后，只保留能生成这个 bestChar 的位置，继续保证 当前前缀仍有可能达到全局最优 。

上面的版是在每一层 $s=i+j$ 做排序，本质是在比较所有候选串：

dp_{i, j} = dp_{parent(i,j)} + g_{i, j}

但事实上最终只要 终点最小串，没必要知道这一层里 第二小、第三小… 。
字典序比较只看 最早不同字符 ，所以可以 逐位构造答案：

设当前已经确定的最小前缀为 $Ans$ （长度 $= t+1$ ）。
维护一个集合 $DP_t$ ：所有能产生这个最小前缀、并且走了 $t$ 步到达的格子。
下一位字符一定是：从 $DP_t$ 出发走一步能到的所有格子里，字母的最小值 $best$ 。
于是 $Ans += best$ ，并把 $DP_{t + 1}$ 更新为：所有能走到字母为 $best$ 的那些格子（去重）。

这就是 DP（分层状态集合）+ 贪心选最小字符 。

DP 初始化与转移

状态

$cur$ 表示 $DP_t$ （当前层可达集合）。
$nxt$ 表示 $DP_{t + 1}$ 。
$Ans$ 当前最小前缀。

初始化

$cur = {(0,0)}$ 。
$Ans = g_{0, 0}$ 。

转移（重复 $2n-2$ 次）

扫描 $cur$ 的所有后继（右、下），取最小字符 $best$ 。
把 $best$ 追加到 $Ans$ 。
再扫描一遍 $cur$ ，把所有后继中字母等于 $best$ 的格子加入 $nxt$ （去重）。
$cur = nxt$ 。

因为每个格子只会在它所属的那一层（对角线）进入集合一次（去重后），所以所有层总入队次数 $\le n^2$ ，每次只看常数个邻居，总复杂度 $O(n^2)$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, vis[N][N];
char g[N][N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
    string Ans;
    Ans.push_back(g[1][1]);
    vector<PII> cur, nxt;
    cur.push_back({1, 1});
    int tim = 1;
    for (int step = 0; step < 2 * n - 2; step++) {
        char best = '{'; // 比 'Z' 大
        // 找下一位最小字符
        for (auto &p : cur) {
            int x = p.fi, y = p.se;
            if (x + 1 <= n) best = min(best, g[x + 1][y]);
            if (y + 1 <= n) best = min(best, g[x][y + 1]);
        }
        Ans.push_back(best);
        // 收集能走到 best 的后继（去重）
        tim++;
        nxt.clear();
        for (auto &p : cur) {
            int x = p.fi, y = p.se;
            if (x + 1 <= n && g[x + 1][y] == best) {
                if (vis[x + 1][y] != tim) {
                    vis[x + 1][y] = tim;
                    nxt.push_back({x + 1, y});
                }
            }
            if (y + 1 <= n && g[x][y + 1] == best) {
                if (vis[x][y + 1] != tim) {
                    vis[x][y + 1] = tim;
                    nxt.push_back({x, y + 1});
                }
            }
        }

        cur.swap(nxt);
    }
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

目前还没有评论...

浅谈棋盘类DP（二）