首页 > 代码库 > 【noi 2.6_2988】计算字符串距离（DP）
【noi 2.6_2988】计算字符串距离（DP）
题意： 给两个字符串，可以增、删、改，问使这两个串变为相同的最小操作数。
解法：（下面2种的代码主要区别在初始化和，而状态转移方程大家可挑自己更容易理解的方法打）
1.f[i][j]表示a串前i个和b串前j个完成匹配的最小操作数。
2.f[i][j]表示a串前i-1个和b串前j-1个完成匹配的最小操作数。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define N 1010 7 8 char a[1010],b[1010]; 9 int f[1010][1010];10 11 int mmin(int x,int y)12 { return x<y?x:y; }13 int main()14 {15 //freopen("a.in","r",stdin);16 int T;17 scanf("%d",&T);18 f[0][0]=0;19 for (int i=1;i<=N;i++)20 f[i][0]=i, f[0][i]=i;21 while (T--)22 {23 scanf("%s%s",a+1,b+1);24 int la=strlen(a+1),lb=strlen(b+1);25 for (int i=1;i<=la;i++)26 for (int j=1;j<=lb;j++)27 {28 f[i][j]=mmin(f[i][j-1]+1,f[i-1][j]+1);//add del29 if (a[i]==b[j]) f[i][j]=mmin(f[i][j],f[i-1][j-1]);30 else f[i][j]=mmin(f[i][j],f[i-1][j-1]+1);//change31 }32 printf("%d\n",f[la][lb]);33 }34 return 0;35 }
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int L=1010; 8 char s[L],ss[L]; 9 int f[L][L];10 void upd(int &x,int y) {x=x<y?x:y;}11 12 int main()13 {14 int n;15 scanf("%d",&n);16 while (n--)17 {18 scanf("%s%s",s+1,ss+1);19 int l=strlen(s+1),ll=strlen(ss+1);20 memset(f,63,sizeof(f));21 f[1][1]=0;22 for (int i=1;i<=l+1;i++)23 for (int j=1;j<=ll+1;j++)24 {25 if (f[i][j]>100010) continue;26 upd(f[i+1][j],f[i][j]+1),upd(f[i][j+1],f[i][j]+1);27 if (s[i]==ss[j]) upd(f[i+1][j+1],f[i][j]);28 else upd(f[i+1][j+1],f[i][j]+1);29 int x=1;30 }31 printf("%d\n",f[l+1][ll+1]);32 }33 return 0;34 }
【noi 2.6_2988】计算字符串距离（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。