最长公共子序列模板(LCS)和LICS模板

递归式：

实例图解：

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int N=111;
 4 int dp[N][N],f[N][N];
 5 char a[N],b[N],c[N];
 6 void LCS(char *a,char *b,int la,int lb)
 7 {
 8     int i,j; 
 9     memset(dp,0,sizeof(dp));
10     for(i=1;i<=la;i++)
11     {
12         for(j=1;j<=lb;j++)
13         {
14             if(a[i-1]==b[j-1])
15             {
16                 dp[i][j]=dp[i-1][j-1]+1;
17                 f[i][j]=0;
18             }
19             else if(dp[i-1][j]>dp[i][j-1])
20             {
21                 dp[i][j]=dp[i-1][j];
22                 f[i][j]=-1;
23             }
24             else
25             {
26                 dp[i][j]=dp[i][j-1];
27                 f[i][j]=1;
28             }
29         }
30     }
31 }
32 void dfs(char *s,int i,int j)
33 {
34     if(!i||!j)  return ;
35     if(!f[i][j])
36     {
37         dfs(s,i-1,j-1);
38         printf("%c",s[i-1]);
39     }
40     if(f[i][j]==1)
41         dfs(s,i,j-1);
42     if(f[i][j]==-1)
43         dfs(s,i-1,j);
44 }
45 int main()
46 {
47     while(scanf("%s%s",a,b)!=EOF)
48     {
49         int la=strlen(a),lb=strlen(b);
50         LCS(a,b,la,lb);
51         printf("%s和%s的最长公共子序列为:
",a,b);
52         dfs(a,la,lb); 
53         puts("");
54         printf("长度为:%d
",dp[la][lb]);
55     }
56     return 0;
57 }

View Code

如果不需要记录路径，可以改成一维数组。

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int N=111;
 4 int dp[N];
 5 char a[N],b[N];
 6 int LCS(char *a,char *b,int la,int lb)
 7 {
 8     int i,j,ma; 
 9     memset(dp,0,sizeof(dp));
10     for(i=1;i<=la;i++)
11     {
12         ma=0; 
13         for(j=1;j<=lb;j++)
14         {
15             if(dp[j]>ma)    ma=dp[j];
16             if(a[i-1]==b[j-1])
17                 dp[j]=ma+1;
18         }
19     }
20     for(i=1;i<=lb;i++)
21         if(dp[i]>ma)    
22             ma=dp[i];
23     return ma;
24 }
25 int main()
26 {
27     while(scanf("%s%s",a,b)!=EOF)
28     {
29         int la=strlen(a),lb=strlen(b);
30         printf("长度为:%d
",LCS(a,b,la,lb));
31     }
32     return 0;
33 }

View Code

在这个基础上，最长递增(减)子序列（LICS）就可以写了。

 1 #include<stdio.h>
 2 #include<string.h> 
 3 const int N=1111;
 4 int dp[N];
 5 int LICS(int *a,int *b,int n,int m)
 6 {
 7     int i,j,ma;
 8     memset(dp,0,sizeof(dp));
 9     for(i=1;i<=n;i++)
10     {
11         ma=0;
12         for(j=1;j<=m;j++)
13         {
14             if(a[i]>b[j]&&dp[j]>ma)
15                 ma=dp[j];
16             if(a[i]==b[j])
17                 dp[j]=ma+1;
18         }
19     }
20     for(i=1;i<=m;i++)
21         if(dp[i]>ma)
22             ma=dp[i];
23     return ma;
24 }
25 int main()
26 {
27     int a[]={0,1,1,6,4,5};
28     int b[]={0,1,2,3,4,5};
29     printf("%d
",LICS(a,b,5,5));
30     return 0;
31 }

View Code

参考文章：http://blog.csdn.net/yysdsyl/article/details/4226630