算法精解:最长公共子序列

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。
其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，
且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
而最长公共子串(要求连续)和最长公共子序列是不同的

设序列 X 存储在数组 x[m]中,序列 Y 存储在数组 y[n]中, 二维数组 L[m+1][n+1]
存储最长公共子序列的长度的迭代过程, S[ m + 1] [n + 1]存储相应的状态, 最长公共子
序列存储在数组 z[ k]中

int CommonOrder(int m, int n, int x[ ] , int y[ ] , int z[ ])

 int i , j , k ; 

 for (j = 0; j j ++ ) // 初始化第 0 行

 L[0][j] = 0;

 for (i = 0; j i++ ) // 初始化第 0 列

 L[i] [0] = 0;

 for (i = 1; i i++ )

 for (j = 1; j j++ )

 if (x[i] == y[j]) { L[i][j] = L[i - 1] [j - 1] + 1; S[i][j] = 1; }

 else if (L[i][j - 1] = L[i - 1][j] ) { L[i][j] = L[i] [j - 1]; S[i][j] = 2; }

 else {L[i][j] = L[i - 1][j]; S[i][j] = 3; }

 i = m; j = n; k = L[m] [n];

 while(i 0 j 0)

 if (S[i][j] == 1) { z[k] = x[i] ; k -- ; i -- ; j -- ; }

 else if (S[i][j] == 2) j -- ;

 else i -- ;

 return L[m][n] ;

int main(void)

 int i,j;

 int x[10] ; 

 int y[10] ; 

 int z[10] ;

 i = CommonOrder(10,10,x,y,z) ;

 printf("%d\n",i) ;

 putchar(\n);

 for(i = 0 ; i 10 ; i++){

 for(j = 0 ; j 10 ; j++){

 printf("%d ",L[i][j]);

 putchar(\n);

 return 0 ;

}

运行结果：

2


0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2

【完虐算法】「字符串-最长公共子序列」全面总结 本来想要把「最长公共子序列」和「最长上升子序列」一起和大家把思路分享一下，都属于可以使用动态规划的思想进行解决。但貌似还是两块内容。 所以，今天先把「最长公共子序列」分享出来和大家聊聊。 后面再出一期把「最长上升子序列」详细的分享，后面这一期内容估计会比较多。
算法笔试模拟题精解之“调整数组” 首先理解题意：经过k次操作后能出现次数最多的元素, 以及这个元素的最小值；然后将示例仔细分析一下，就可以找到解题的方法了。
算法笔试模拟题精解之“连绵的群山” 可以将山化分为几个小连续区间，每个区间保证越来越高，并且保证每个区间尽可能的长。除第一个和最后一个区间，中间的其余区间，有移除可能的是每个区间的最小值和最大值，第一个区间有移除可能的是最小值，最后一个区间有移除可能的是最大值。这样才能找出最长的山的区间。
算法笔试模拟题精解之“数组染色” 可以采用链表的思想，定义一个数组temp来存放每个递增的子串，题目需要求出最少的递增子串有多少个，采取的思路是递增的子串越密集越好。
算法笔试模拟题精解之“最大矩形面积” 根据题意，想要组成面积最大的矩形，需要有最大的长与宽，并且组成长与宽的木棍都需要有2根，因此，只要选择最大的两组木棍即可组成最大的矩形。
算法笔试模拟题精解之“最大边权和” 根据题意，最终需要将n个点连通并达到最大边权，而边权为两个点的点权之和的一半，所以一个点加入连通图的最大边权就是和点权最大的点连通。
morixinguan ITGEGE在线教育嵌入式开发讲师。 CSDN博客专家、CSDN-Linux特邀编辑、CSDN博乐、CSDN学院讲师，目前从事嵌入式开发领域，从事与单片机，Linux，android相关的产品开发。