最长公共子序列(LCS)

定义 (维基百科)

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

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

这类问题通常都是采用动态规划的思想来解决，核心就是构造出动态解决方程。

以两个序列 X、Y 为例子：
　　设有二维数组dp[i,j]表示X的第i位和Y的第j位之前的最长公共子序列的长度，则有：

dp[i,j]={dp[i−1][j−1]+1(X[i]==Y[j])max{dp[i−1,j],dp[i,j−1]}(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} dp[i,j]={dp[i−1][j−1]+1max{dp[i−1,j],dp[i,j−1]}​(X[i]==Y[j])(X[i]!=Y[j])​

时间复杂度和空间复杂度都是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
    }
}