【问题求解II-HW5.B】最长公共子序列

求字符串的最长公共子序列长度是一个经典的动态规划入门问题。该问题有如下非常经典的状态设计和转移“套路”：

令 $dp(i, j)$ 表示 $s[1…i]$ 和 $t[1..j]$ 这两个串的最长公共子序列长度，那么最终答案显然为 $dp(|s|, |t|)$。转移考虑 $s[i]$ 和 $t[j]$ 是否在最长公共子序列中：

• 若 $s[i]$ 不在最长公共子序列中，则可以从 $dp(i-1, j)$ 转移来。
• 若 $t[j]$ 不在最长公共子序列中，则可以从 $dp(i, j-1)$ 转移来。
• 若 $s[i]$ 和 $t[j]$ 都在公共子序列中 (注意它们是最后一个字符，所以它们一定要能匹配上 (相同))，则可以从 $dp(i-1, j-1)+1$ 转移来。

对以上三种情况取最大值即可。该动态规划的时间复杂度和空间复杂度均为 $O(|s||t|)$。

本题的特别之处在于 $s$ 很长而 $t$ 很短，且 $|s||t|$ 超出了我们能够承受的范围 (无论是时间还是空间)，因此前面提到的传统做法不太奏效。本题希望让大家明白的是：对于求极值的动态规划问题，状态和值之间通常可以互相转化。一个动态规划问题通常有若干个变量 (记为 $m$ 个)，动态规划状态会固定住其中的 $m-1$ 个变量，动态规划的值则是剩下的那个变量的极值。对于大部分人来说，最自然的选择是将题目要求的那个变量作为动态规划的值，但有时为了缩减状态数，我们会选择“看起来别扭”的设计，将取值空间小的那些变量作为动态规划的状态。

以本题为例，本题的变量有三个：$s$ 的前缀长度，$t$ 的前缀长度，最长公共子序列的长度。因为本题求的是第三个，所以前面提到的传统状态设计最容易让人理解。但在本题的数据范围下，你会发现 $s$ 的前缀长度有 $10^6$ 种可能，而后两者的取值空间都是 $10^3$，因此我们来设计如下一种“看起来很奇怪的状态”：

令 $dp(i, j)$ 表示考虑 $t[1…i]$，如果想要获得长度为 $j$ 的最长公共子序列，$s$ 的前缀至少要取到哪里 (如果做不到则值为 $|s|+1$)。虽然听起来很拗口，但转移仍然可行。考虑以下情形：

• 最长公共子序列不包含 $t[i]$，则可以从 $dp(i-1, j)$ 直接转移来。
• 最长公共子序列包含 $t[i]$，从 $dp(i-1, j-1)$ 转移来。记 $x=dp(i-1, j-1)$，现在的状况是：$s[1…x]$ 和 $t[1…i-1]$ 有一个长度为 $j-1$ 的公共子串。我们要从 $x+1$ 往后继续延伸，找到第一个和 $t[i]$ 相同的字符匹配上从而达到要求。因此我们可以预处理一个数组 $nxt(i, ch)$ 表示从 $s[i]$ 开始第一个字符 $ch$ 出现在哪里 (这并不困难，留给大家作为思考)。

我们把取值空间小的两个状态作为动态规划的状态，把最大的那个作为值。值是不需要在执行过程中枚举的，因此我们有效优化了复杂度。该做法的时间复杂度和空间复杂度均为 $O(|t|^2)$。