【培训试题】编辑距离1374
Description
设A和B是两个字符串。我们用最少的字符操作，将字符串A转换为字符串B。这里所说的字符操作包括： (1)删除一个字符； (2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串A转换为字符串B所用的最少字符操作数称为字符串A到字符串B的编辑距离，记为δ(A，B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离δ(A，B)。
Input:两行，每行代表一个字符串（串长小于200） Output:一个数，代表两者的最小编辑距离 Sample Input
ab ac
Sample Output:
1 【试题分析】 1、阶段和状态：
f[i][j]：表示将A的前i个字符变成B的前j个字符的最少操作次数 求f[i][j]要考虑3种操作：
(1).在A中删除一个字符：f[i-1][j] (2).在A中插入一个字符：f[i][j-1]
(3).在A中将一个字符改为另一个字符，如果a[i]=b[i]为f[i-1][j-1],如果a[i]!=b[i]为f[i-1][j-1]+1。 2、状态转移方程：
f[i][j]=min{f[i-1][j-1](a[i]=b[i]);min{f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1}} 初始化：f[0][i]=f[i][0]=i; answer=f[a1][b1]
3、核心子程序： cin>>s1>>s2; l1=s1.length();l2=s2.length(); for(i=l1;i>0;i--) s1[i]=s1[i-1];//s1=’ ’+s1; for(i=l2;i>0;i--) s2[i]=s2[i-1]; memset(f,0,sizeof(f)); for(i=1;i<=l1;i++) f[i][0]=i; for(i=1;i<=l2;i++) f[0][i]=i; for(i=1;i<=l1;i++) for(j=1;j<=l2;j++) if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]; else f[i][j]=min(f[i-1][j-1]+1,min(f[i-1][j]+1,f[i][j-1]+1)); cout< Description 回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的 任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。 Input 第一行包含一个整数N，表示给定字符串的长度（3≤N≤50 00）。 第二行是一个长度为N的字符串。字符串仅由大写字母“A”到“Z”，小写字母“a”到“z”和数字“0”到“9”构成。大写字母和小写字母将被认为是不同的。 Output 只有一行，包含一个整数，表示需要插入的最少字符数。 Sample Input 5 Ab3bd Sample Output 2 【试题分析】 1、阶段和状态： 设f(i,j)表示使得S的[1..i]和[j..n]部分构成回文需要添加的最少字母个数 。 2、状态转移方程： f(i-1,j)+1, f(i,j)=min f(i,j+1)+1, f(i-1, j+1), S(i)=S(j) 边界为f(0,n+1)=0 Ans=min{f(i, i), f(i,i+1)} 3、核心子程序： int f[5005][5005]={0};string s; int main() { long n,i,j,ans; cin>>n>>s;s=' '+s; for(i=1;i<=n;i++){f[0][i]=n-i+1;f[i][n+1]=i;} for(i=1;i<=n;i++) for(j=n;j>=i;j--) if(s[i]==s[j])f[i][j]=f[i-1][j+1]; else f[i][j]=min(f[i-1][j],f[i][j+1])+1; ans=9999999; for(i=0;i<=n;i++) { if(f[i][i+1]0&&f[i][i]