本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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 指示动态规划中的顺序，然后逆推即可。