dp,時間複雜度O(n^3),f[i][j][k]表示a串到i，b串到j的時候，比對了c串的k位，要用滾動數組
代碼
1 #include<cstring>
2 #include<algorithm>
3 #include<cstdio>
4 using namespace std;
5 const int N = 510;
6 char a[N],b[N],c[N];
7 int l1,l2,l3,i,j,k,f[N][N][2],now;
8 int main()
9 {
10 scanf("%s",a);
11 scanf("%s",b);
12 scanf("%s",c);
13 l1=strlen(a);
14 l2=strlen(b);
15 l3=strlen(c);
16 for (k=0;k<=l3;k++)
17 {
18 now=1-now;
19 for (i=0;i<=l1;i++)
20 for (j=0;j<=l2;j++)
21 if (i+j+k)
22 {
23 f[i][j][now]=-0x37373737;
24 if (i) f[i][j][now]=max(f[i][j][now],f[i-1][j][now]);
25 if (j) f[i][j][now]=max(f[i][j][now],f[i][j-1][now]);
26 if (i&&j)
27 if (a[i-1]==b[j-1])
28 {
29 f[i][j][now]=max(f[i][j][now],f[i-1][j-1][now]+1);
30 if (k)
31 if (a[i-1]==c[k-1])
32 f[i][j][now]=max(f[i][j][now],f[i-1][j-1][now^1]+1);
33 }
34 }
35 }
36 if (f[l1][l2][now]<0)
37 printf("NO SOLUTION");
38 else
39 printf("%d\n",f[l1][l2][now]);
40 } 轉載于:https://www.cnblogs.com/fzmh/p/5457748.html