线性动态规划：最短公共超序列（Shortest Common Supersequence） 题目描述： 给定两个字符串 s1 和 s2 ，要求找出一个最短的字符串 S ，使得 s1 和 s2 都是 S 的子序列（即 s1 和 s2 中的字符按顺序出现在 S 中，但不必连续）。你需要返回这个最短公共超序列的长度。 例如： 输入：s1 = "abac", s2 = "cab" 输出：长度 5（最短公共超序列可以是 "cabac" 或 "abacab" 等） 解题思路 步骤 1：理解问题本质 最短公共超序列（SCS）的长度可以通过以下关系推导： 设 LCS(s1, s2) 为两个字符串的最长公共子序列长度。 最短公共超序列的长度 = len(s1) + len(s2) - LCS(s1, s2) 。 为什么？ 因为公共超序列需要包含 s1 和 s2 的所有字符，但公共部分（LCS）只需出现一次，因此减去重复计算的公共部分长度。 步骤 2：动态规划定义状态 定义 dp[i][j] 表示字符串 s1 的前 i 个字符和 s2 的前 j 个字符的 最长公共子序列长度 。 i 范围：0 到 len(s1) j 范围：0 到 len(s2) 初始条件： dp[0][j] = 0 （空字符串与任何字符串的 LCS 长度为 0）， dp[i][0] = 0 。 步骤 3：状态转移方程 如果 s1[i-1] == s2[j-1] （当前字符相同）： dp[i][j] = dp[i-1][j-1] + 1 如果 s1[i-1] != s2[j-1] （当前字符不同）： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) （因为当前字符不同时，LCS 可能来自 s1 少一个字符或 s2 少一个字符的情况） 步骤 4：计算最短公共超序列长度 先计算 LCS_length = dp[len(s1)][len(s2)] 最短公共超序列长度 = len(s1) + len(s2) - LCS_length 举例演示 以 s1 = "abac", s2 = "cab" 为例： 构建 dp 表 （行对应 s1，列对应 s2，索引从 0 开始）： 初始化：第一行和第一列为 0。 计算过程： i=1, j=1: s1[ 0]='a', s2[ 0]='c' → 不同 → dp[1][1] = max(dp[0][1], dp[1][0]) = max(0,0) = 0 i=1, j=2: 'a' vs 'a' → 相同 → dp[1][2] = dp[0][1] + 1 = 0+1 = 1 i=1, j=3: 'a' vs 'b' → 不同 → dp[1][3] = max(dp[0][3], dp[1][2]) = max(0,1) = 1 继续填充完整表（最终 dp[4][3] = 2 ，LCS 为 "ab" 或 "ac"）。 最短公共超序列长度 ： len(s1) + len(s2) - LCS_length = 4 + 3 - 2 = 5 进阶思考：如何输出最短公共超序列？ 若需要输出具体超序列，可在 dp 表基础上反向追踪： 从 (len(s1), len(s2)) 开始： 若 s1[i-1] == s2[j-1] ，将该字符加入结果，移动到 (i-1, j-1) 。 若不同，比较 dp[i-1][j] 和 dp[i][j-1] ： 若 dp[i-1][j] 更大，将 s1[i-1] 加入结果，移动到 (i-1, j) 。 否则将 s2[j-1] 加入结果，移动到 (i, j-1) 。 最后将剩余字符按顺序加入。 反转结果字符串即为最短公共超序列。 总结 本题通过 LCS 动态规划间接求解 SCS，核心是理解 超序列长度 = 两字符串长度和 - 公共子序列长度 。动态规划表填充时间复杂度 O(n* m)，空间可优化至 O(min(n,m))。