算法：最长公共子序列（LCS）

1. 什么是 LCS ？

先看几个概念

• 字符子串：指的是字符串中连续的n个字符，如abcdefg中，ab、cde、fg 都是它的子串。
• 字符子序列：指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如abcdefg中，acdg、bdf 是它的子序列，而bac、dbfg则不是。
• 公共子序列：如果序列 C 既是序列 A 的子序列，同时也是序列 B 的子序列，则称它为序列 A 和序列 B 的公共子序列。

LCS 是 Longest Common Subsequence 的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。

注：LCS 不一定是唯一的，但长度是一定的。

例如：CTCA、TCGA 都是字符串 CATCGA 和字符串 GTACCGTCA 的 LCS。

2. 基本策略 ？

... 传说中的 ...

线性规划

图文无关

3. 程序代码

4. 特性分析

• 时间复杂度：O(m*n)