【动态规划】最大子序列

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int length;
 5 int c[20][20];
 6 int b[20][20];
 7 char f[20],s[20];
 8 
 9 void l(int m,int n)
10 {
11     int i,j;
12     for(i=1;i<=m;i++)c[i][0]=0;
13     for(j=1;j<=n;j++)c[0][j]=0;
14 //    if(f[0]==a[0])
15     for(i=1;i<=m;i++){
16         for(j=1;j<=n;j++){
17                 if(f[i]==s[j]){
18                     c[i][j]=c[i-1][j-1]+1;
19                     b[i][j]=1;
20                 }else if(c[i-1][j]>=c[i][j-1]){
21                     c[i][j]=c[i-1][j];
22                     b[i][j]=2;
23                 }else {
24                     c[i][j]=c[i][j-1];
25                     b[i][j]=3;
26                 }
27 
28     }
29     }
30 
31 }
32 
33 void LCS(int m,int n)
34 {
35     if(m==0||n==0)return;
36     if(b[m][n]==1)
37     {
38         LCS(m-1,n-1);
39         printf("%c",f[m]);
40     }else if(b[m][n]==2)
41     {
42         LCS(m-1,n);
43     }else
44     {
45         LCS(m,n-1);
46     }
47 }
48 int main()
49 {
50     gets(f);
51     gets(s);
52     int m=strlen(f),n=strlen(s);
53     l(m,n);
54     printf("%d\n",c[m][n]);
55     LCS(m,n);
56     return 0;
57 }