902. 最短编辑距离

1 问题描述

给定两个字符串 $A$ 和 $B$，现在要将 $A$ 经过若干操作变为 $B$，可进行的操作有：

1. 删除–将字符串 $A$ 中的某个字符删除。
2. 插入–在字符串 $A$ 的某个位置插入某个字符。
3. 替换–将字符串 $A$ 中的某个字符替换为另一个字符。

现在请你求出，将 $A$ 变为 $B$ 至少需要进行多少次操作。

输入格式

第一行包含整数 $n$，表示字符串 $A$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $A$。

第三行包含整数 $m$，表示字符串 $B$ 的长度。

第四行包含一个长度为 $m$ 的字符串 $B$。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

$1 \leq n, m \leq 1000$

2 问题求解

2.1 操作规范化

• 删除：记为 $D_i$，删除下标为 $i$ 的字符，将从下标 $i$ 起的字符向左移动一位。
• 插入：记为 $I_{i, c}$，将从下标为 $i$ 起的字符向右移动一位，在下标为 $i$ 处填字符 $c$。
• 替换：记为 $R_{i, c}$， 将下标为 $i$ 的字符替换为 $c$。

PS：为了方便 $2.2$ 说明，我们将操作 $op$ （ $D$ 或 $I$ 或 $R$） 的第一个下标 $i$ 称为操作目标。称操作目标顺序排列的操作序列为正规操作序列，否则为一般操作序列。

以 $AGTCTGACGC$ 和 $AGTAAGTAGGC$ 为例，变换序列 $T$ 可以表示为：
$$T=R_{4, A}R_{5, A}I_{7, T}R_{9, G}$$

2.2 引理：任意操作序列都存在效果相同且长度相等的正规操作序列

考察对于串 $a$ 的操作序列 $s$，对于交换其中相邻的两个操作：
$$s = …op_i op_{i+1}…$$
$op_i op_{i+1}$ 表示的可能情况有：

• $D_{j}D_{k}$
• $D_{j}I_{k, x}$
• $D_jR_{k, x}$
• $I_{j, x}D_k$
• $I_{j, x}I_{k, y}$
• $I_{j, x}R_{k, y}$
• $R_{j, x}D_k$
• $R_{j, x}I_{k, y}$
• $R_{j, x}R_{k, y}$

以交换 $I_{j, x}D_k$ 为例：

• 当 $k < j$ 时，$I_{j, x}D_k$ 变为 $D_kI_{j-1, x}$，新序列与原序列作用效果不变；
• 当 $k = j$ 时，$I_{j, x}D_k$ 变为 $D_kI_{j-1, a[k]}$，其中 $a$ 为未进行 $op_i$ 前状态下的串，新序列与原序列作用效果不变；
• 当 $k > j$ 时，$I_{j, x}D_k$ 变为 $D_{k-1}I_{j, x}$，新序列与原序列作用效果不变；

其余操作组合的交换也存在类似的变换方式，使得新序列与原序列作用效果不变。

在已知交换相邻操作的变换的基础上，通过多次进行相邻操作交换，可以实现操作序列 $s$ 的任意两个两个操作 $op_i$ 和 $op_j$ 的交换。

因此，对于任意操作序列，通过交换操作，总可以找到一个效果相同且长度相等的正规操作序列。

2.3 动态规划

2.3.1 状态表示

• 集合：记 $S_{i,j}$ 为将 $a_{1:i}$ 变为 $b_{1:j}$ （左右都闭）的正规操作序列集合。求一般操作序列集合中操作序列最小长度的问题，等价于求该一般操作序列集合对应的的正规操作序列集合中操作序列最小长度的问题。

• 属性：定义操作序列集合S上的函数 $f$，其中$f(S)$ 表示 $S$ 中所有操作序列长度的最小值。

2.3.2 状态转移

根据 $S_{i,j}$ 中正规操作序列的最后一个操作，可以将 $S_{i,j}$ 分为：

• $S^D_{i, j}$：对 $a_i$进行删除操作，也就是$D_{j+1}$。因为操作目标时递增的，因此该情况说明在进行最后一个操作前的操作将 $a_{1:i-1}$ 变为 $b_{1:j}$，即这些部分操作所对应的集合应为 $S_{i-1, j}$。此时：
  $$f(S^D_{i, j}) = f(S_{i-1, j}) + 1$$

• $S^I_{i, j}$：在 $a_i$ 后面增加一个字符 $b_j$，也就是$I_{j+1, b_j}$。同理，该情况说明在进行最后一个操作前的操作将 $a_{1:i}$ 变为 $b_{1:j-1}$，即这些部分操作所对应的集合应为 $S_{i, j-1}$。此时：
  $$f(S^I_{i, j}) = f(S_{i-1, j}) + 1$$

• $S^R_{i, j}$：将 $a_i$ 替换为字符 $b_j$，也就是$R_{j, b_j}$(说明$a_i \neq b_j$）。同理，该情况说明在进行最后一个操作前的操作将 $a_{1:i-1}$ 变为 $b_{1:j-1}$，即这些部分操作所对应的集合应为 $S_{i-1, j-1}$。此时：
  $$f(S^R_{i, j}) = f(S_{i-1, j-1}) + 1$$

• $S^E_{i, j}$：（E for else）最后一个操作并没有对 $a_i$ 进行操作，即并没有影响到 $a_i$（说明$a_i=b_j$）。因此该操作序列集合也可以将 $a_{1:i-1}$ 变为 $b_{1:j-1}$，即应有 $S^E_{i, j} = S_{i-1, j-1}$。此时：
  $$f(S^E_{i, j}) = f(S_{i-1, j-1})$$

综上所述，当 $a_i=b_j$ 时，$f(S_{i,j})$ 应为：
$$f(S_{i,j}) = max(f(S_{i-1, j}) + 1, f(S_{i-1, j}) + 1, f(S_{i-1, j-1}))$$
当 $a_i\neq b_j$ 时，$f(S_{i,j})$ 应为：
$$f(S_{i,j}) = max(f(S_{i-1, j}) + 1, f(S_{i-1, j}) + 1, f(S_{i-1, j-1}) + 1)$$

2.4 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;

char a[N], b[N];

int dp[N][N];

int main()
{
    memset(dp, 0x3f3f3f3f, sizeof dp);

    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> a[i];

    cin >> m;

    for (int i = 1; i <= m; i ++) cin >> b[i];

    for (int i = 0; i <= N; i ++) dp[i][0] = i, dp[0][i] = i;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            // 最后一步是删除, 最后一步操作前a[1 ~ i-1] = b[1 ~ j] 
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            // 最后一步是插入, 最后一步操作前a[1 ~ i] = b[1 ~ j-1] 
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);

            // 最后一步是替换, 最后一步操作前a[1 ~ i-1] = b[1 ~ j-1]
            if (a[i] != b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            // 最后一步没有操作a[i], 说明a[i] = b[j]
            else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}