ECNUOJ 2857 编辑距离

编辑距离

Time Limit:5000MS Memory Limit:65536KB
Total Submit:314 Accepted:128

Description 

有两个字符串（仅有英文小写字母组成）A，B。我们可以通过一些操作将A修改成B。操作有三种：1修改一个字母，2删除一个字母，3插入一个字母。现在定义编辑距离为将A通过上述操作修改成B的最少次数。

Input 

第一行有一个正整数N，表示有多少组测试数据

接下来有2*N行，每两行代表一组数据。每组数据的第一行是一个起始字符串A，第二行是目的字符串B。

Output 

对于每组数据，输出一个值，表示将A修改成B的编辑距离、每组数据占一行，不要有多余空格。

N<=100 , A，B字符串的长度不超过500

Sample Input 

2
hello
hi
apple
google

Sample Output 

4
4

Source

解题：动态规划，dp[i][j]表示源串S前i个字符转成目标串T的前j个字符需要的最短编辑距离。

那么我们有如果S[i] == T[j]那么直接把dp[i][j] 就等于 dp[i-1][j-1]，因为这个相等，就不需要操作次数

如果S[i] != T[j] 那么我们有三种选择，增加、删除以及修改，我们先考虑修改，如果把S[i]修改为T[j]，那么dp[i][j] = dp[i-1][j-1]+1

如果我们要把S[i]删除，那么dp[i][j] = dp[i-1][j] + 1也就是说用前面的S[i-1]就能变成T[j]

如果我们选择增加 那么dp[i][j] = dp[i][j-1] + 1 也就是说，我们已经可以把S前面i个经过最短的编辑距离变为T[j-1]现在要变成T[j]，我们可以选择在S[i]后面加上T[j]，这样

S[i]就可以经过最短的编辑距离变成T[j]了。记得取最小就是了

 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
char sa[maxn],sb[maxn];
int dp[maxn][maxn];
int main() {
    int kase;
    scanf("%d",&kase);
    while(kase--) {
        scanf("%s%s",sa,sb);
        int n = strlen(sa);
        int m = strlen(sb);
        memset(dp,0x3f,sizeof dp);
        for(int i = 0; i <= n; ++i) dp[i][0] = i;
        for(int i = 0; i <= m; ++i) dp[0][i] = i;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j) {
                dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);
                dp[i][j] = min(dp[i][j],dp[i-1][j-1] + (sa[i-1] != sb[j-1]));
            }
        printf("%d
",dp[n][m]);
    }
    return 0;
}