LCS Longest (maximum) common subsequence

资 源 简 介

LCS Longest (maximum) common subsequence

详 情 说 明

最长公共子序列（Longest Common Subsequence, LCS）是计算机科学中经典的动态规划问题，用于寻找两个序列共有的、相对顺序一致的最长子序列。与子串不同，子序列不要求连续，仅需保持字符的原始先后顺序。

核心思路 LCS通常通过动态规划高效求解。构建二维表格，行列分别对应两个序列的字符。表格中的每个单元格记录截止当前位置的LCS长度： 若当前字符匹配，则LCS长度由左上角单元格值+1； 若不匹配，继承左侧或上方单元格的较大值。

优化方向 空间优化：将二维表格压缩为两行或一维数组； 变种扩展：支持多序列LCS或加权LCS； 应用场景：文本差异比对（如Git）、生物信息学（DNA序列对齐）。

该算法体现了动态规划"分治+记忆化"的核心思想，时间复杂度O(mn)，适合中等规模数据。