1.问题

定义
设 X 和 Z 是两个序列，其中
X = <x1,x2….,xm>
Z = <z1,z2,….,zk>
如果存在X的元素构成的按下标严格递增序列<xi1,xi2,….,xik>,使xij = zj,j=1,2,….,k.那么Z是X的子序列，Z含有的元素个数，称为子序列的长度
按下标递增，比如X中的i1到i多少是1,3,6,7，可以不连续，但需要递增
定义
设X和Y是两个序列，如果Z既是X的子序列，也是Y的子序列，则称Z是X和Y的公共子序列
实例：
X = <A,B,C,B,D,A,B>
Y = <B,D,C,A,B,A>
<B,C,B,A>
<B,C,A,B>
问题
最长公共子序列问题（Longest Common Subsequence-序列，LCS）,给定任意两个序列，求两者的最长公共子序列。

2.解析

Xi = <x1,x2,…,xi>
Yj = <y1,y2,….,yj>
Zk = <z1,z2,…,zk>

如果Zk是Xi和Yj的最长公共子序列—全局最优解

（1）xi = yj，那么zk = xi = yj ， Zk-1是Xi-1 和Yj -1 的最长公共子序列—局部最优解
（2） xi≠yj,zk≠xi那么Zk是Xi-1和Yj 的最长公共子序列
（3）xi ≠ yj ,zk ≠yj , 那么Zk是Xi和Yj -1的最长公共子序列

如下公式对应着上面三个推论：

3. 设计

C++伪代码
算法1：给出最长子串长度—通过长度知道在两者如此长度时，对字串是怎么样的处理态度（删除还是存储）

C[0,j] = C[i,0] = 0,1≤≤m,1≤j≤n
For i = 1 to m
For j =1 to n

算法2：f(B,i,j)输出最长字串—递归算法—通过B得到如何处理串
If I = 0 or j = 0 then return;
If B[i,j] = ← //删除两个
f(B,i-1,j-1)
Then 输出 X[i]
Else if B[i,j] = ↑ f(B, i-1, j) //删除X
Else f(B,i,j-1)

实验图片~：

4. 分析

三个for循环，时间复杂度：O(n3)

5. 源代码地址

https://github.com/Lin02993/Algorithm-Analysis-and-Practice-on-the-job