最短编辑距离

输入

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; // 删除
    
    
    
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            // f[i][j - 1] : 表示的是前面 i 个和 j - 1 个成功匹配，还需要进行插入
            
            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;
}