最长公共子序列 (LCS)

给定序列的子序列只是去除了一些元素的给定序列。

给定两个序列 X 和 Y，如果 Z 既是 X 的子序列又是 Y 的子序列，则我们说序列 Z 是 X 和 Y 的公共序列。

在最长公共子序列问题中，我们给定两个序列 X = (x₁ x₂....x_m) 和 Y = (y₁ y₂ y_n)，希望找到 X 和 Y 的最大长度公共子序列。LCS 问题可以使用动态规划解决。

最长公共子序列的特征

一种蛮力方法是找到 X 的所有子序列，并检查每个子序列是否也是 Y 的子序列，这种方法需要指数时间，因此对于长序列来说是不切实际的。

给定序列 X = (x₁ x₂.....x_m)，我们将 X 的第 i 个前缀定义为 i=0, 1, 和 2...m，即 X_i= (x₁ x₂.....x_i)。例如：如果 X = (A, B, C, B, C, A, B, C)，则 X₄= (A, B, C, B)

LCS 的最优子结构：设 X = (x₁ x₂....x_m) 和 Y = (y₁ y₂.....y_n) 为序列，Z = (z₁ z₂......z_k) 为 X 和 Y 的任意 LCS。

• 如果 x_m = y_n，则 z_k=x_m=y_n 且 Z_k-1 是 X_m-1 和 Y_n-1 的 LCS
• 如果 x_m ≠ y_n，则 z_k≠ x_m 意味着 Z 是 X_m-1 和 Y 的 LCS。
• 如果 x_m ≠ y_n，则 z_k≠y_n 意味着 Z 是 X 和 Y_n-1 的 LCS

第二步：递归解决方案：LCS 具有重叠子问题属性，因为要查找 X 和 Y 的 LCS，我们可能需要查找 X_m-1 和 Y_n-1 的 LCS。 如果 x_m ≠ y_n，那么我们必须解决两个子问题，找到 X 和 Y_n-1 的 LCS。 无论这些 LCS 中哪一个更长，都是 x 和 y 的 LCS。 但是每个子问题都有找到 X_m-1 和 Y_n-1 的 LCS 的子问题。

令 c [i,j] 为序列 X_i 和 Y_j 的 LCS 长度。如果 i=0 或 j =0，则其中一个序列的长度为 0，因此 LCS 的长度为 0。 LCS 问题的最佳子结构给出了递归公式

第三步：计算 LCS 的长度：设两个序列 X = (x₁ x₂.....x_m) 和 Y = (y₁ y₂..... y_n) 作为输入。 它将 c [i,j] 值存储在表 c [0......m,0..........n] 中。维护表 b [1..........m, 1..........n]，这有助于我们构建最优解。 c [m, n] 包含 X,Y 的 LCS 的长度。