Hellc

【题目描述】

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：

(1) 删除一个字符；

(2) 插入一个字符；

(3) 将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试编写程序，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。

【题目链接】

CodeVS 2598 编辑距离问题

【解题思路】

线性DP，设$f[i][j]$表示A的长度为$i$的前缀和B的长度为$j$的前缀之间的编辑距离，之所以设长度而不设下标，是因为涉及到空串的问题，用下标的话边界不好处理。

转移： $$ f[i][j] = \cases { f[i - 1][j - 1] & A[i - 1] = B[j - 1] \\ min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1 & A[i - 1] ≠ B[j - 1] } $$

当前两个字符相同时，无需操作，直接等于上一位。 不同时，有三种可选的操作 (1)编辑到$i, j - 1$然后删除A的最后一个字符。 (2)编辑到$i - 1, j$然后在A最后面增加一个字符。 (3)编辑到$i - 1, j - 1$然后修改最后一位使其和B相同。 取最小值。

边界，任何串到空串的编辑距离为该串本身的长度。 $$ f[0][0] = 0 $$

$$ f[i][0] = i $$

$$ f[0][j] = j $$

【AC代码】

采用递推决策实现，注意下标。

#include <cstdio>
#include <algorithm>
#include <cstring>

#define MAXN 4000

char A[MAXN + 1], B[MAXN + 1];
int f[MAXN + 1][MAXN + 1];

inline int min(const int &a, const int &b, const int &c){
    return std::min(std::min(a, b), c);
}

int main(){
    scanf("%s\n%s", A, B);
    int n = strlen(A), m = strlen(B);

    f[0][0] = 0;
    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++){
        int &ans = f[i][j];
        if(A[i - 1] == B[j - 1]) ans = f[i - 1][j - 1];
        else ans = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
    }
    printf("%d\n", f[n][m]);
    return 0;
}

就是这样啦