题目

Description

假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。
下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。
例如：a="ABC",b="CBCD",则a与b的编辑距离为2。
你的任务就是：编一个快速的程序来计算任意两个字符串的编辑距离。

Input

输入包含多组测试数据。每组测试数据一行，为字符串A和字符串B。
字符串的长度不大于1024，且全为字母。

Output

编辑距离。

Sample Input

ABC CBCD

Sample Output

2

题解

数据包括两个字符串,类似于最长公共子序列的形式
可以类似的使用一个二维的 dp[i][j] 来表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最短编辑距离

当我们计算 dp[i][j] 时,显然我们已经有了 dp[i][j-1] 、 dp[i-1][j] 、 dp[i-1][j-1]

• 如果 a[i] == b[j] (对应的字符相等),则加上这两个字符,对答案无影响
  也即 dp[i][j] = dp[i-1][j-1]
  同时,也可以是 a 或 b 少一个字符的情况下增加一个字符,即 dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + 1
• 如果 a[i] != b[j] (对应的字符不同),则需要进行修改操作
  有3种修改方式:
  • 修改字符:将其中一个字符变成另一个字符
    即 dp[i][j] = dp[i-1][j-1] + 1
  • 增删字符(a):将字符串 a 的字符删掉
    可以理解为:字符串 a 少一个字符时,加上 b 对应的字符
    即 dp[i][j] = dp[i-1][j] + 1
  • 增删字符(a):将字符串 b 的字符删掉
    可以理解为:字符串 b 少一个字符时,加上 a 对应的字符
    即 dp[i][j] = dp[i][j-1] + 1

同时如果两个字符的长度差为 delta 则编辑距离最少为 delta

注意好边界值即可

一开始迷之TLE,即使AC了也无法理解

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

typedef unsigned int LL;

const int maxn = 1050;
char a[maxn],b[maxn];

LL dp[maxn][maxn];


bool Do() {
    if(scanf("%s%s",a,b) == EOF)
        return false;

    LL lena = strlen(a);
    LL lenb = strlen(b);

    for(unsigned int i = 1;i <= lena;i++)
        for(unsigned int j = 1;j <= lenb;j++) {
            int ita = i - 1;
            int itb = j - 1;
            LL delta = (i > j) ? (i - j) : (j - i);
            LL Min = min(dp[i][j - 1],dp[i - 1][j]) + 1;
            if(a[ita] == b[itb]) {
                dp[i][j] = min(dp[i - 1][j - 1],Min);
            } else {
                dp[i][j] = min(dp[i - 1][j - 1] + 1,Min);
            }
            dp[i][j] = max(dp[i][j],delta);
        }

    printf("%u\n",dp[lena][lenb]);
    return true;
}
int main() {
    dp[0][0] = 0;
    for(int i = 1;i < maxn;i++) 
        dp[0][i]=dp[i][0] = i;
    while(Do());
    return 0;
}