AcWing 902. 最短编辑距离

题目

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

1. 删除–将字符串 $A$ 中的某个字符删除。
2. 插入–在字符串 $A$ 的某个位置插入某个字符。
3. 替换–将字符串 $A$ 中的某个字符替换为另一个字符。 现在请你求出，将 $A$ 变为 $B$ 至少需要进行多少次操作。

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

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

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

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

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

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

数据范围 $1≤n,m≤1000$ 输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

4

思路

由动态规则常用思路：
状态表示 -- 集合：将A[1-i]变成B[1-j]的操作次数的集合。
        -- 属性：数量
状态计算 -- 对A操作与对B操作等价，可以只看A或只看B，这里看A

当遍历到 $i、j$ 时，存在以下情况：

1. $A$ 删除第 $i$ 个字符--说明 $A[i - 1] == B[j], f[i, j] = f[i - 1][j] + 1$
2. $A$ 增加一个字符--前提为 $A[i] == B[j - 1], f[i, j] = f[i][j - 1] + 1$
3. 替换：当 $A[i] == B[j]$，则没有替换的必要 $f[i, j] = f[i - 1][j - 1]$；否则 $A[i - 1] == B[j - 1], f[i, j] = f[i - 1][j - 1] + 1$

代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    cin >> n >> a + 1 >> m >> b + 1;
    
    // 初始化边界的值
    for (int i = 0; i <= n; i ++ ) f[i][0] = i;
    for (int i = 0; i <= m; i ++ ) f[0][i] = i;
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
        
    cout << f[n][m] << endl;
    
    return 0;
}