【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 del

29          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);//change

31        }

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）

最新文章

热门文章