关于算法-数据结构:最长公共子序列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}
}

关于算法-数据结构:最长公共子序列LCS

定义 (维基百科)

解决方案