网站开发用台式机电脑配置,网站静态和伪静态意思,哈尔滨seo优化培训,国外经典平面设计网站题目描述 设A和B是两个字符串。我们要用最少的字符操作次数#xff0c;将字符串A转换为字符串B。这里所说的字符操作共有三种#xff1a; 1、删除一个字符#xff1b; 2、插入一个字符#xff1b; 3、将一个字符改为另一个字符#xff1b; #xff01;皆为小写字母将字符串A转换为字符串B。这里所说的字符操作共有三种 1、删除一个字符 2、插入一个字符 3、将一个字符改为另一个字符 皆为小写字母 输入输出格式 输入格式 第一行为字符串A第二行为字符串B字符串A和B的长度均小于2000。 输出格式 只有一个正整数为最少字符操作次数。 输入输出样例 输入样例#1 sfdqxbw gfdgw 输出样例#1 4
解题思路我们可以用f[i][j]表示从a[i]到b[i]的最短编辑距离。然后推出动态转移方程f[i][j]min(f[i-1][j-1]1,f[i-1][j]1,f[i][j-1]1)f[i-1][j-1]1 表示改变该字符 f[i-1][j]1 表示删去一个字符 f[i][j-1]1 表示插入一个字符 代码#includecstdio
#includecstring
#includeiostream
using namespace std;
int f[2002][2002],n,m;
char s1[2002],s2[2002];
int main()
{scanf(%s%s,s1,s2);//输入字符串mstrlen(s1);nstrlen(s2);//确定长度for (int i1;im;i) f[i][0]i;//将s1的1-i变为空串就是删去i个字符编辑距离为ifor (int i1;in;i) f[0][i]i;//同上for (int i1;im;i)for (int j1;jn;j)if (s1[i-1]s2[j-1]) f[i][j]f[i-1][j-1];//如果两个字符一样就不需编辑else {f[i][j]min(min(f[i-1][j-1]1,f[i-1][j]1),f[i][j-1]1);//求三种情况的最小值}printf(%d,f[m][n]);//输出a的1-m全部到b的1-n全部的最短编辑距离return 0;
}
