浅谈序列对齐DP

[[LCS模型]] 解决的是这样一个标准问题：给定两个序列，在保持各自相对顺序的前提下，寻找一个尽可能长的公共子序列。

但在实际问题中，两个序列之间不一定只是“相同元素才能匹配”。字符可以被替换，也可以与空位对应，每一种对应方式还可能具有不同的代价或得分。

因此，我们可以从两个方向去展开这个问题：

1. 一次对齐可以怎样变化：两个元素能否匹配，跳过元素的代价是多少，最终求最大得分还是最小代价；
2. 基础状态还需要保存什么：输出具体方案、统计最优方案，或者限制选中的位置必须组成若干连续段。

零、从典题得到状态的定义

1. 为什么需要同时记录两个前缀

问题

AT_dp_f LCS - 洛谷
给定字符串 $S$ 和 $T$，输出它们的一条最长公共子序列。

数据规模：$|S|,|T|\le 3000$。

最直接的想法是枚举其中一个字符串的子序列，再判断它是否也是另一个字符串的子序列，但子序列数量是指数级的，显然不可行。

公共子序列中的每个字符都要同时对应到两个字符串中的某个位置。如果只记录字符串 $S$ 处理到了哪里，我们不知道字符串 $T$ 中已经使用到了哪里；反过来也一样。

因此，需要同时记录两个字符串的处理进度。定义 $f[i][j]$ 表示字符串 $S$ 的前 $i$ 个字符与字符串 $T$ 的前 $j$ 个字符的最长公共子序列长度。

这里选择两个前缀作为状态，是因为后续的匹配，只与两个字符串当前分别处理到哪里有关，而不需要知道此前具体跳过了哪些字符。

2. 最后两个字符怎样处理

考虑两个前缀的最后位置 $S_i$ 与 $T_j$，我们直接枚举最后一步。

• 不选择 $S_i$，答案来自 $f[i-1][j]$；
• 不选择 $T_j$，答案来自 $f[i][j-1]$；
• 若 $S_i=T_j$，可以让这两个字符匹配，答案来自 $f[i-1][j-1]+1$。

于是完整转移为：

$$f[i][j] = \max \begin{cases} f[i-1][j],\\ f[i][j-1],\\ f[i-1][j-1]+1 \qquad (S_i=T_j). \end{cases}$$

当 $S_i=T_j$ 时，选择这对相同字符一定不会比单独跳过其中一个更差，因此可以化简为：

$$f[i][j] = \begin{cases} f[i-1][j-1]+1, & S_i=T_j,\\ \max(f[i-1][j],f[i][j-1]), & S_i\ne T_j. \end{cases}$$

边界为：$f[i][0]=f[0][j]=0$。

▶

LCS模板

int f[maxn][maxn];

void solve( ) {
    string s, t;
    cin >> s >> t;
    int n = s.size( ), m = t.size( );
    s = " " + s, t = " " + t;

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            if( s[i] == t[j] ) f[i][j] = f[i-1][j-1] + 1;
            else f[i][j] = max( f[i-1][j], f[i][j-1] );
        }
    }
    cout << f[n][m] << '\n';
}

3. 如何输出一条具体方案

二维状态不仅保存了最优值，也保存了最优答案从哪里转移而来。

从 $(n,m)$ 反向回溯：

• 若 $S_i=T_j$，当前字符可以进入答案，同时令 $i,j$ 减一；
• 否则走向答案值没有变小的上方或左方状态。

▶

LCS 方案回溯

string ans;
int i = n, j = m;

while( i && j ) {
    if( s[i] == t[j] ) {
        ans.push_back( s[i] );
        i --, j --;
    } else if( f[i-1][j] >= f[i][j-1] ) {
        i --;
    } else {
		j --;
    }
}

reverse( ans.begin( ), ans.end( ) );
cout << ans << '\n';

4. 从 LCS 中提取标准模型

LCS 的三个转移可以理解为：

1. f[i-1][j-1] : A <-> B | 匹配两个字符
2. f[i][j-1]   : A <-> . | 跳过 Ai
3. f[i-1][j]   : . <-> B | 跳过 Bj

因此，对于两个序列 $A, B$，可以定义 $f[i][j]$ 表示处理完 $A$ 的前 $i$ 个元素与 $B$ 的前 $j$ 个元素时，能够得到的最优答案。

若三种对应方式的贡献分别为：$w(A_i, B_j), w(A_i, -), w(-, B_j)$，就得到了一种统一的转移骨架：

$$f[i][j] = opt \begin{cases} f[i-1][j-1] + w(A_i,B_j),\\ f[i-1][j] + w(A_i,-),\\ f[i][j-1] + w(-,B_j). \end{cases}$$

其中 opt 为 max 或 min。若某种对应方式不合法，删除对应的转移。第一行和第一列由一个序列为空时的处理方式决定。

如果两个字符不同，也允许放在同一列，会得到什么问题？

一、一次对齐可以怎样变化

1. 编辑距离

问题

P2758 编辑距离
给定两个字符串 $A$ 和 $B$。每次可以插入、删除或替换一个字符，求将 $A$ 变为 $B$ 的最少操作次数。

数据规模：$|A|,|B|\le 2000$。

如果直接从 “当前字符串长什么样” 入手，会发现这并不好处理，因为插入和删除会不断改变字符串长度，后续字符的位置也会随之移动。

换一个角度，直接考虑最终两个字符串如何逐列对应。

• 保留或替换：让 $A_i$ 与 $B_j$ 对应；
• 删除 $A_i$：让 $A_i$ 与空位对应；
• 插入 $B_j$：让空位与 $B_j$ 对应。

这样，三种编辑操作恰好对应 LCS 中的三种基础转移。

定义：$f[i][j]$ 表示将 $A$ 的前 $i$ 个字符变成 $B$ 的前 $j$ 个字符所需的最少操作次数。

由此我们得到本题的转移方程：

$$f[i][j] = \min \begin{cases} f[i-1][j-1]+[A_i\ne B_j],\\ f[i-1][j]+1,\\ f[i][j-1]+1. \end{cases}$$

当一个字符串为空时，只能连续删除或插入： $f[i][0] = i$，$f[0][j] = j$。

▶

P2758

ll f[maxn][maxn];

int calc( char a, char b ) {
    if( a == b ) return 0;
    else return 1;
}

void solve( ) {
    string s, t;
    cin >> s >> t;
    int n = s.size( ), m = t.size( );
    s = " " + s, t = " " + t;

    for( int i = 1; i <= n; ++ i ) f[i][0] = i;
    for( int j = 1; j <= m; ++ j ) f[0][j] = j;

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            f[i][j] = inf;
            f[i][j] = min( f[i][j], f[i-1][j-1] + calc( s[i], t[j] ) );
            f[i][j] = min( f[i][j], f[i-1][j] + calc( s[i], ' ' ) );
            f[i][j] = min( f[i][j], f[i][j-1] + calc( ' ', t[j] ) );
        }
    }
    cout << f[n][m] << '\n';
}

若是不允许替换呢？

若不允许替换，最终保留下来的字符必须同时出现在两个字符串中，并保持原有顺序，因此它们构成一个公共子序列。

为了减少操作次数，应尽可能多地保留字符，也就是保留一条最长公共子序列。设 $L = LCS(A,B)$，则需要删除 $n - L$ 个字符，再插入 $m - L$ 个字符，答案为：$ans = n + m - 2L$。

普通编辑距离中，每种操作的代价都是 $1$。如果不同字符之间的距离也不相同，状态还需要改变吗？

2. P1279 字串距离

问题

P1279 字串距离
给定两个仅包含小写字母的字符串 $A,B$。可以在字符串的任意位置插入空格，得到两个等长的扩展串。两个非空格字符对应的代价为 ASCII 码差的绝对值，字符与空格对应的代价为 $K$，求两个字符串的最小距离。

数据规模：$|A|,|B|\le 2000,\ 1\le K\le 100$。

本题已经给出了特殊情况下的距离，所以我们可以直接套用双前缀状态定义：$f[i][j]$ 表示 $A$ 的前 $i$ 个字符与 $B$ 的前 $j$ 个字符进行对齐时的最小距离。

三种对应方式变为：

1. $A_i$ 与 $B_j$ 对应，代价为 $|A_i-B_j|$；
2. $A_i$ 与空位对应，代价为 $K$；
3. 空位与 $B_j$ 对应，代价为 $K$。

因此得到转移：

$$f[i][j] = \min \begin{cases} f[i-1][j-1]+|A_i-B_j|,\\ f[i-1][j]+K,\\ f[i][j-1]+K. \end{cases}$$

当另一个字符串为空时，所有字符都只能与空格对应，因此：$f[i][0]=iK$，$f[0][j]=jK$。

▶

P1279

ll f[maxn][maxn];
int k;

int calc( char a, char b ) {
    if( a == ' ' || b == ' ' ) return k;
    return abs( a - b );
}

void solve( ) {
    string s, t;
    cin >> s >> t;
    int n = s.size( ), m = t.size( );
    s = " " + s, t = " " + t;

    k = read( );

    for( int i = 1; i <= n; ++ i ) f[i][0] = i * k;
    for( int j = 1; j <= m; ++ j ) f[0][j] = j * k;

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            f[i][j] = inf;
            f[i][j] = min( f[i][j], f[i-1][j-1] + calc( s[i], t[j] ) );
            f[i][j] = min( f[i][j], f[i-1][j] + calc( s[i], ' ' ) );
            f[i][j] = min( f[i][j], f[i][j-1] + calc( ' ', t[j] ) );
        }
    }
    cout << f[n][m] << '\n';
}

但这样可能会产生一个错误的直觉：既然 $A_{i}$ 和 $B_{j}$ 都还没有处理，就直接让它们对应。

但可能将两个字符分别与空格对应会令总代价更小，举个例子：$A_{i} = a, B_{j} = z, k = 3$，直接对应的代价为 $25$，而分开对应只需要 $6$。

那还要加特判吗？其实不用，这题在转移过程中会从三种转移中取得处理这种代价更小的情况。

下面再看一道类似的题。

3. 相似基因

问题

P1140 相似基因
给定两个基因序列，以及字符 A C G T - 之间的评分表。可以在两个序列中插入空位，求最大相似度。
数据规模：$n \le 100$。

这题跟上面那题的对齐方式完全相同，定义：$f[i][j]$ 表示第一个基因前 $i$ 个碱基与第二个基因前 $j$ 个碱基对齐时的最大得分。

若评分函数为 $tab(x,y)$，则：

$$f[i][j] = \max \begin{cases} f[i-1][j-1] + tab(A_i,B_j),\\ f[i-1][j] + tab(A_i,-),\\ f[i][j-1] + tab(-,B_j). \end{cases}$$

这题的转移并不难，坑点在于边界情况的处理，实际上，当另一条序列为空时，每个字符都必须与空格对应，并产生对应的得分，因此。

$$\begin{aligned} f[i][0] = f[i-1][0] + tab(A_i, -) \\ f[0][j] = f[0][j-1] + tab(-, B_j) \\ \end{aligned}$$

▶

P1140

const int tab[5][5] = {
    {5, -1, -2, -1, -3},
    {-1, 5, -3, -2, -4},
    {-2, -3, 5, -2, -2},
    {-1, -2, -2, 5, -1},
    {-3, -4, -2, -1, 0}
};

int id( char ch ) {
    if( ch == 'A' ) return 0;
    if( ch == 'C' ) return 1;
    if( ch == 'G' ) return 2;
    if( ch == 'T' ) return 3;
    return 4;
}

int a[maxn], b[maxn];
int f[maxn][maxn];

void solve( ) {
    int n, m;
    string s1, s2;
    cin >> n >> s1 >> m >> s2;

    for( int i = 1; i <= n; ++ i ) a[i] = id( A[i-1] );
    for( int j = 1; j <= m; ++ j ) b[j] = id( B[j-1] );
    
    memset( f, 128, sizeof f );
    f[0][0] = 0;

    for( int i = 1; i <= n; ++ i ) f[i][0] = f[i-1][0] + tab[a[i]][4];
    for( int j = 1; j <= m; ++ j ) f[0][j] = f[0][j-1] + tab[b[j]][4];

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            f[i][j] = max( f[i][j], f[i][j-1] + tab[b[j]][4] );
            f[i][j] = max( f[i][j], f[i-1][j] + tab[a[i]][4] );
            f[i][j] = max( f[i][j], f[i-1][j-1] + tab[a[i]][b[j]] );
        }
    }
    cout << f[n][m] << '\n';
}

这三题都没有扩展双前缀的状态，从本质上没有区别，只是修改了 $w$ 成本函数的计算方式。

如果不只要求计算一个最优解，这个基础状态还有效吗？

二、在基础状态上增加信息

1. LCS 计数

问题

P2516 最长公共子序列
给定两个字符串，求 LCS 长度，以及不同最长公共子序列的数量。

数据规模约为 $5000$，答案对 $10^8$ 取模。

只求 LCS 长度时，每个状态保存一个最优值即可。现在还要求不同最优方案的数量，因此增加：$g[i][j]$ 表示两个前缀中不同的 LCS 的数量。

那么状态转移就从 LCS 的推导中同时完成计数：

if( A[i] == B[j] ) {
	f[i][j] = f[i-1][j-1] + 1;
	g[i][j] = g[i-1][j-1];
} else {
	f[i][j] = max( f[i-1][j], f[i][j-1] );
	if( f[i][j] == f[i-1][j] ) g[i][j] += g[i-1][j];
	if( f[i][j] == f[i][j-1] ) g[i][j] += g[i][j-1];
	// 容斥原理
	if( f[i][j] == f[i-1][j-1] ) g[i][j] -= g[i-1][j-1];
}

边界状态为：$g[i][0] = g[0][j] = 1$。因为任意字符串与空串只有一种公共子序列，即空串。

这是一种最优方案计数的问题，不局限于这个 LCS 模型，在 [[计数类DP]] 问题中，思路通用：先计算最优值，合并所有能到达最优值的前驱状态，再对重复方案进行容斥。

2. 连续段限制

问题

P2679 子串
从字符串 $A$ 中取出恰好 $K$ 个互不重叠的非空子串，按顺序拼接成字符串 $B$，求方案数。

数据规模：$n\le 1000,\ m\le 200,\ K\le m$。

这道题仍然要求保持两个字符串中的相对顺序，但 $A$ 中被选中的位置不能任意分散，而要组成恰好 $K$ 个连续子串。

最先想到的状态是：$dp[k][i][j]$ 表示从 $A$ 的前 $i$ 个字符中选出 $k$ 段，拼成 $B$ 的前 $j$ 个字符的方案数。

接着考虑转移，我们就会发现问题，处理 $A_{i}$ 时，我们无法判断当前匹配是 接在上一段后面，还是在当前位置新开一段。

所以还需要记录最后一个位置是否被选择，定义：$f[k][i][j]$ 表示从 $A$ 的前 $i$ 个字符中取出 $k$ 段，匹配到 $B$ 的前 $j$ 个字符，并且 $A_i$ 必须被选中的方案数。

只有当 $A_i=B_j$ 时，$A_i$ 才能匹配 $B_j$。

• $A[i]$ 跟在上一段后：既然段数没变 ，那么就可以从 $(k, i - 1, j - 1)$ 转移过来。
• $A[i]$ 新起了一段：有点麻烦，能确定的是 $( k - 1, ?, j - 1 )$，不好说是从哪个 $i$ 转移的。

由于状态已经是 $\mathcal{O}(nmk)$ 数量级，转移必须控制在 $\mathcal{O}(1)$ 的数量级，为了方便第二种情况的转移，我们再定义：$g[k][i][j] = \sum_{x=1}^{i}f[k][x][j]$，表示最后一个被选位置不超过 $i$ 的总方案数。

tile

for( int k = 1; k <= kk; ++ k ) {
	for( int i = 1; i <= n; ++ i ) {
		for( int j = 1; j <= m; ++ j ) {
			if( A[i] == B[j] ) f[k][i][j] = ( f[k][i-1][j-1] + g[k-1][i-1][j-1] ) % mod;
			else f[k][i][j] = 0;
			g[k][i][j] = ( f[k][i][j] + g[k][i-1][j] ) % mod;
		}
	}
}

边界状态为：$g[0][i][0]=1$。

朴素保存全部 $f[k][i][j]$ 与 $g[k][i][j]$ 需要较大空间，而当前段数 $k$ 只依赖 $k-1$，因此可以滚动段数这一维。

▶

P2679

int f[2][maxn][maxm];
int g[2][maxn][maxm];

void solve( ) {
    int n = read( ), m = read( ), k = read( );
    string A, B;
    cin >> A >> B;
    A = ' ' + A, B = ' ' + B;

    for( int i = 0; i <= n; ++ i )  g[0][i][0] = 1;
    
    int cur = 1;
    for( int t = 1; t <= k; ++ t ) {
        int pre = cur ^ 1;
        memset( f[cur], 0, sizeof( f[cur] ) );
        memset( g[cur], 0, sizeof( g[cur] ) );
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= m; ++ j ) {
                if( A[i] == B[j] ) f[cur][i][j] = ( f[cur][i-1][j-1] + g[pre][i-1][j-1] ) % mod;
                else f[cur][i][j] = 0;
                g[cur][i][j] = ( f[cur][i][j] + g[cur][i-1][j] ) % mod;
            }
        }
        cur ^= 1;
    }
    cur ^= 1;
    cout << g[cur][n][m] << '\n';
}

连续段限制常见做法是扩展状态：当前已使用的段数。

三、抽象统一模型

双前缀状态是因为后续匹配同时依赖两个序列各自处理到的位置，不是因为出现了两个字符串就机械的开二维数组。

同样，增加状态也不是看到额外条件就机械地加一维，而是判断：这个信息是否会影响后续仍然允许怎样转移。

序列对齐 DP 的核心可以理解为：

双前缀状态 → 枚举最后一列的对应方式 → 初始化第一行第一列 → 修改局部贡献或扩展必要状态