动态规划之 LCS（最大公共子序列）

__ryp__ · 2023-12-14 18:27:18 · 个人记录

LCS 是动态规划的经典问题。

求 LCS 的长度

我们用 dp[i][j] 表示序列 A_1 \cdots A_i 与 B_1 \cdots B_j 的 LCS 长度。dp[i][j] 之间有什么关系？也即，状态之间应当怎样转移？

我们可以分情况讨论。

• 当 A_i = B_j 时，这个新的 LCS 长度就是上一个 LCS 的长度加上一。这是明显的。

• 否则，新的 LCS 长度是前两个 LCS 长度中的最大值。

所以，当 a[i] == b[j] 时 dp[i][j] = dp[i - 1][j - 1] + 1，否则，dp[i][j] = max (dp[i - 1][j], dp[i][j - 1])

求 LCS 序列

为了求 LCS 序列，我们需要维护一个 dir 指示动态规划中的顺序，然后逆推即可。