最长公共子序列(LCS) 算法-数据结构

定义 (维基百科) 【最长公共子序列(LCS)】在一个序列集合中（通常为两个序列）查找所有序列中最长的子序列。
这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。

最长公共子序列问题是一个经典的计算机科学问题，
也是数据比较程序，比如 Diff工具和生物信息学应用的基础。
它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变

解决方案这类问题通常都是采用动态规划的思想来解决，核心就是构造出动态解决方程。
以两个序列 X、Y 为例子：
设有二维数组dp[i,j]表示X的第i位和Y的第j位之前的最长公共子序列的长度，则有：
$$ dp[i,j]= \begin{cases} dp[i-1][j-1]+1& \text{(X[i]==Y[j])}\\ max\{dp[i-1,j],dp[i,j-1]\}& \text{(X[i]!=Y[j])} \end{cases} $$

时间复杂度和空间复杂度都是O(mn)。

力扣水题

func longestCommonSubsequence(text1 string, text2 string) int { len1, len2 := len(text1), len(text2) if len1 == 0 || len2 == 0 { return 0 }commonSub := make([][]int, len1+1, len1+1) // 初始化二维数据 for i := 0; i <= len1; i++ { commonSub[i] = make([]int, len2+1, len2+1) }for i := 0; i < len1; i++ { for j := 0; j < len2; j++ { if text1[i] == text2[j] { commonSub[i+1][j+1] = commonSub[i][j] + 1 } else { commonSub[i+1][j+1] = max(commonSub[i][j+1], commonSub[i+1][j]) } } } return commonSub[len1][len2] }func max(a, b int) int { if a > b { return a } else { return b } }