求答疑：基于LCS的DP表生成的最小超序列的正确性证明

一、证明它是最小长度的超序列 #

设两个输入字符串为 S（长度 m）和 T（长度 n），它们的最长公共子序列（LCS）长度为 l。

• 任何合法超序列必须包含 S 的全部 m 个字符和 T 的全部 n 个字符，但LCS的 l 个字符是两者共有的，直接合并时会被重复计算两次。因此，超序列的理论最小长度为 m + n - l——这是无法再缩小的下界，因为必须覆盖所有独有字符，同时公共字符仅需保留一次。
• 基于DP表构造的超序列，恰好是将 S 和 T 中不属于LCS的字符按顺序加入，同时LCS的字符仅保留一次，最终总长度就是 m + n - l，完全匹配理论最小长度，因此它是最小的。

二、证明它是合法超序列（保持原字符串顺序） #

要证明这一点，需要结合DP表的回溯构造逻辑分析：

回溯构造的核心规则（从DP表右下角 dp[m][n] 向左上角回溯） #

• 若 S[i] == T[j]：该字符属于LCS，将其加入结果集合，然后同时向左上移动（i--，j--）。
• 若 dp[i][j] == dp[i-1][j]：说明 S[i] 不在LCS中，将其加入结果集合，向上移动（i--）。
• 若 dp[i][j] == dp[i][j-1]：说明 T[j] 不在LCS中，将其加入结果集合，向左移动（j--）。
• 当 i > 0 或 j > 0 时，继续处理剩余字符，直到 i == 0 且 j == 0。最后将结果集合反转，得到最终超序列。

顺序保持的证明 #

1. S 的字符顺序保持：
   S 中的任意两个字符 s_a 和 s_b，若在原 S 中 s_a 出现在 s_b 前面（即 i_a < i_b），回溯时 s_b 会先被处理（无论是否属于LCS），因此会先被加入结果集合。反转结果后，s_a 就会回到 s_b 前面，与原 S 的顺序完全一致。

2. T 的字符顺序保持：
   同理，T 中的任意两个字符 t_c 和 t_d，若原 T 中 t_c 出现在 t_d 前面（j_c < j_d），回溯时 t_d 先被处理并加入结果，反转后 t_c 位于 t_d 之前，与原 T 顺序一致。

3. LCS字符的双重顺序兼容：
   LCS本身就是同时保持 S 和 T 顺序的公共子序列，因此回溯时加入的LCS字符，在最终超序列中的顺序既符合 S 的要求，也符合 T 的要求。

综上，基于LCS DP表构造的序列既满足最小长度要求，又完全符合超序列的顺序要求，是合法的最小超序列。

内容的提问来源于stack exchange，提问作者myfakeaccount