1728 - Edit
有二个字串 str1, str2 , 字串str2 可以经过若于次变换后变成str1，其变换的规则是：
1） 可以在任何位置加入字符；
2） 可以删除任何字符；
3） 可以改变任何字符。
约定：增加、删除与改变任何一个字符称为一次变换。
例如：str1=‘bcadef ’ str2=’abcedkk’
<span style="font-size:14px;"> 可以经过的变换为：</span>
<span style="font-size:14px;"> 1）删去第一个字符‘a’ str2=’bcedkk’</span>
<span style="font-size:14px;"> 2）改变一个字符，将‘e’变成‘a’ str2=’bcadkk’</span>
<span style="font-size:14px;"> 3）改变一个字符，将‘k’变成‘e’ str2=’bcadek’</span>
<span style="font-size:14px;"> 4） 改变一个字符，将‘k’变成‘f’ str2=’bcadef’</span>
<span style="font-size:14px;"> 此时，str2 经过4次变换后变成str1。</span>
<span style="font-size:14px;"> 问题：给出str1，str2，要求用最少的变换次数从str2变换为str1 。</span>
题目输入
多笔测资，每笔测资两行
第一行：字符串s1
第二行：字符串s2
题目输出
对每笔测资，输出一个整数，表示该组的最少变换次数。
输入/输出样例
题目输入
bcadef abcedkk
题目输出
4
提示
动态规划
C语言解答
#include "stdio.h" int L[1001][1001]; char a[1000],b[1000]; int d1,d2; int min(int a,int b,int c) { if(a>b) a=b; if(a>c) a=c; return a; } int main() { int i,j; while(gets(a)!=NULL) { gets(b); d1=strlen(a); d2=strlen(b); for(i=0,j=0;j<=d2;j++) L[i][j]=j; for(i=0,j=0;i<=d1;i++) L[i][j]=i; for(i=0;i<d1;i++) for(j=0;j<d2;j++) if(a[i]==b[j]) L[i+1][j+1]=L[i][j]; else L[i+1][j+1]=min(L[i+1][j]+1,L[i][j+1]+1,L[i][j]+1); printf("%d\n",L[d1][d2]); } return 0; }
C++解答
#include<iostream> #include<string> #include<cstring> #include<algorithm> using namespace std; int f[255][255]={0}; int main() { string s1,s2; int i,j,len1,len2; while (cin>>s1>>s2) { memset(f,0x7f,sizeof(f)); f[0][0]=0; len1=s1.size(); len2=s2.size(); for (i=0;i<=len1;i++) for (j=0;j<=len2;j++) if (i>0||j>0) if (i>0&&j>0&&s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]; else { if (j>0) f[i][j]=min(f[i][j],f[i][j-1]+1); //删除 if (i>0&&j>0) f[i][j]=min(f[i][j],f[i-1][j-1]+1); //改写 if (i>0) f[i][j]=min(f[i][j],f[i-1][j]+1); //插入 } cout<<f[len1][len2]<<endl; } return 0; }
提示
动态规划