题目名称	1181. 编辑距离
输入输出	`edita.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	苏轼于2012-10-18加入
开放分组	全部用户
提交状态
分类标签	动态规划
	分享题解

通过：79，提交：155，通过率：50.97%
GaoErFu	100	0.000 s	0.00 MiB	C++
521	100	0.000 s	0.00 MiB	C++
dateri	100	0.000 s	0.00 MiB	C++
风吹我已散	100	0.000 s	0.00 MiB	C++
莫知	100	0.000 s	0.00 MiB	C++
风吹我已散	100	0.000 s	0.00 MiB	C++
TARDIS	100	0.000 s	0.42 MiB	C++
4	100	0.000 s	0.89 MiB	C++
嗨嗨嗨	100	0.001 s	2.12 MiB	C++
超人	100	0.002 s	4.23 MiB	C++

关于编辑距离的近10条评论(全部评论)
我不是什么好人，直接亮明码 `#include <fstream> #include <cstring> using namespace std; const int MAXN(1001); int n, m, k, f[MAXN][MAXN]; char s[MAXN], t[MAXN]; main() { ifstream a("edita.in"); ofstream o("edita.out"); a >> s; n = strlen(s); a >> t; m = strlen(t); 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]=min(min(f[i-1][j],f[i][j-1])+1,f[i-1][j-1]+(int)(s[i-1]!=t[j-1])); o << f[n][m]; }` 啊吧啦吧啦吧 2015-07-31 19:17 3楼
字串距离的简化版。王者自由 2012-10-29 17:32 2楼
注意边界的处理天下第一的吃货殿下 2012-10-21 16:58 1楼

关于 编辑距离 的近10条评论(全部评论)

我不是什么好人，直接亮明码

#include <fstream>

#include <cstring>

using namespace std;

const int MAXN(1001);

int n, m, k, f[MAXN][MAXN];

char s[MAXN], t[MAXN];

main()

{

 ifstream a("edita.in");

 ofstream o("edita.out");

 a >> s;

 n = strlen(s);

 a >> t;

 m = strlen(t);

 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]=min(min(f[i-1][j],f[i][j-1])+1,f[i-1][j-1]+(int)(s[i-1]!=t[j-1]));

 o << f[n][m];

}

啊吧啦吧啦吧

2015-07-31 19:17 3楼

字串距离的简化版。

王者自由

2012-10-29 17:32 2楼

注意边界的处理

天下第一的吃货殿下

2012-10-21 16:58 1楼

1181. 编辑距离

★☆ 输入文件：edita.in 输出文件：edita.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

字符串是数据结构和计算机语言里很重要的数据类型，在计算机语言中，对于字符串我们有很多的操作定义，因此我们可以对字符串进行很多复杂的运算和操作。实际上，所有复杂的字符串操作都是由字符串的基本操作组成。例如，把子串a替换为子串b，就是用查找、删除和插入这三个基本操作实现的。因此，在复杂字符串操作的编程中，为了提高程序中字符操作的速度，我们就应该用最少的基本操作完成复杂操作。

在这里，假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。

我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。

下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a；那么，把字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。

例如，如a=“ABC”，b=“CBCD”，则a与b的编辑距离为2。

你的任务就是：编一个最快的程序来计算任意两个字符串的编辑距离。

【输入格式】

第1行为字符串a；第2行为字符串b。

【输出格式】

编辑距离。

【样例1输入】

ABC
CBCD

【样例1输出】

【样例2输入】

DCDBDC
ADDCDD

【样例2输出】

【提示】

注：字符串的长度不大于1000，字符串中的字符全为大写字母。