在生物信息学中常常需要比较两个或多个DNA序列的相似程度。DNA是由碱基分子组成的串。这些碱基是腺嘌呤adenine、鸟嘌呤guanine、胞嘧啶cytosine和胸腺嘧啶thymine常常用它们对应英文单词的第一个字母表示分别为A、G、C 和T。例如一种组织的DNA序列为S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA而另一种组织的序列为S2=GTCGTTCGGAATGCCGTT

（在原题基础上略作修改）

算法1

(动态规划) $O(n^2)$

本题要求的是最长公共子序列，而不是最长公共子串，因此不能直接应用求最长公共子串的算法。最长公共子序列问题可以使用动态规划求解。

设 $dp_{i,j}$ 表示 $s1$ 前 $i$ 个字符和 $s2$ 前 $j$ 个字符的最长公共子序列长度，则有：

$$ dp_{i,j}=\begin{cases} 0 & i=0\text{ 或 }j=0 \ dp_{i-1,j-1}+1 & s1_i=s2_j \ \max(dp_{i-1,j},dp_{i,j-1}) & s1_i\not=s2_j \end{cases} \ $$

最终的结果即为 $dp_{n,m}$，其中 $n$ 和 $m$ 分别为 $s1$ 和 $s2$ 的长度。

求出 $dp_{i,j}$ 后，可以通过反向追踪从 $dp_{n,m}$ 开始，根据当前位置 $dp_{i,j}$ 的值和相邻位置的值，决定是否将 $s1_i$ 加入到公共子序列中，反向追踪即可得到具体的公共子序列。

时间复杂度

动态规划算法的时间复杂度为 $O(n^2)$，其中 $n$ 为 $s1$ 和 $s2$ 的长度。

Java 代