LCS問題，狀態轉移方程為f[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1,若a[i]=b[j]則f[i][j]=f[i-1][j-1]

#include<cstdio> #include<cstring> #define max(a,b)a>b?a:b #define INF 1000005 int t,i,j,k,l1,l2,q; char a[2005],b[2005]; int f[2005][2005]; int min(int a,int b){return a<b?a:b;} int main(){scanf("%d",&t);while(t--){scanf("%s%s",a,b);l1=strlen(a);l2=strlen(b);for(i=0;i<=l1;i++)f[i][0]=i;for(i=0;i<=l2;i++)f[0][i]=i;q=max(l1,l2);for (i=1;i<=l1;i++)for (j=1;j<=l2;j++){f[i][j]=INF;if (a[i-1]==b[j-1])f[i][j]=f[i-1][j-1];f[i][j]=min(min(min(f[i-1][j],f[i-1][j-1]),f[i][j-1])+1,f[i][j]);}printf("%d\n",f[l1][l2]); } }

?

轉載于:https://www.cnblogs.com/moris/p/4323821.html

總結

以上是生活随笔為你收集整理的SPOJ Problem 6219:Edit distance的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。