大白话介绍LCS(最长公共子序列)

今日学习了七月在线的算法课程，再次加深了对LCS的理解，现将相关内容整理如下：

LCS（Longest Common Subsequence）即最长公共子序列。

若从一个序列S中任意删除若干字符后形成新序列T，则称T为S的子序列。

对于两个序列X与Y而言，它们的公共子序列中长度最长的那个即被定义为X与Y的最长公共子序列。

举例说明如下：

字符串13455与245576的最长公共子序列为455。

字符串acdfg与adfc的最长公共子序列为adf。

需要特别注意的是，此处应与最长公共子串（Longest Common Substring）区分开来。后者要求所提取的字符串必须是连续的。

此处为了节省时间，直接引用了教师提供的PPT内容。请记住以下相关符号。

以下将对LCS问题的求解方法进行探讨：

若x与y相等时：

随后即可获得如下结果：

![](https://cdl.itadn.