最短编辑距离

最短编辑距离

输入

10
AGTCTGACGC
11
AGTAAGTAGGC

输出

4

题解

首先我们将 *** 作划分为四个部分， 删除、 插入、 替换、 不 *** 作

代码如何书写？

对 每一步 先执行插入和删除 *** 作，取最小值，进一步判断当前是否可以进行替换 或者不 *** 作来降低 *** 作步数。

代码实现

#include 
using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N]; // 表示前 i 个字符串和前 j 个字符串已经匹配成功。

int main() {
    
    scanf("%d %s", &n, a + 1);
    scanf("%d %s", &m, b + 1);
    
    for (int i = 1; i <= n; i ++ ) f[i][0] = i; // 插入
    for (int i = 1; i <= m; i ++ ) f[0][i] = i; // 删除
    
    /*
        i = 0 : 1 2 3 4 5 6 7 8 9 10 11 
        i = 1 : 0 1 2 3 4 5 6 7 8 9 10 
        i = 2 : 1 0 1 2 3 4 5 6 7 8 9 
        i = 3 : 2 1 0 1 2 3 4 5 6 7 8 
        i = 4 : 3 2 1 1 2 3 4 5 6 7 7 
        i = 5 : 4 3 2 2 2 3 3 4 5 6 7 
        i = 6 : 5 4 3 3 3 2 3 4 4 5 6 
        i = 7 : 6 5 4 3 3 3 3 3 4 5 6 
        i = 8 : 7 6 5 4 4 4 4 4 4 5 5 
        i = 9 : 8 7 6 5 5 4 5 5 4 4 5 
        i = 10: 9 8 7 6 6 5 5 6 5 5 4 
    
    */
    
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            // f[i][j - 1] : 表示的是前面 i 个和 j - 1 个成功匹配，还需要进行插入
            /*
                无论他们相不相等，先执行插入和删除 *** 作，以达到最小值，再判断是否可以通过不 *** 作降低f[i][j]
            
            */
            f[i][j] = min(f[i][j - 1], f[i - 1][j]) + 1; 
            
            // 这里表示利用 f[i - 1][j - 1]的 *** 作步数进行更新， 因为前i - 1, j - 1经过 *** 作后已经相等
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
        
    }
    
    cout << f[n][m];
    
    return 0;
}