线性动态规划：最长公共子序列的变种——最短公共超序列

题目描述
给定两个字符串 s1 和 s2，要求找出一个最短的字符串，使得 s1 和 s2 都是这个字符串的子序列。输出这个最短公共超序列的长度。例如：

• 输入：s1 = "abac", s2 = "cab"
• 输出：长度 5（超序列可以是 "cabac"，其中 "abac" 和 "cab" 都是其子序列）。

解题思路
最短公共超序列（Shortest Common Supersequence, SCS）的长度可以通过最长公共子序列（LCS）推导出来。关键观察是：超序列需要包含 s1 和 s2 的所有字符，但公共部分（即 LCS）只需包含一次。因此，SCS 的长度为：

\[\text{len}(s1) + \text{len}(s2) - \text{len}(LCS(s1, s2)) \]

动态规划的状态定义与 LCS 类似，但最终结果的计算方式不同。

步骤详解

1. 状态定义
   设 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的 LCS 长度。

   • i 的范围是 0 到 len(s1)，j 的范围是 0 到 len(s2)。
   • 当 i=0 或 j=0 时，dp[i][j] = 0（空字符串的 LCS 长度为 0）。

2. 状态转移方程

   • 如果 s1[i-1] == s2[j-1]（当前字符匹配），则：

\[ dp[i][j] = dp[i-1][j-1] + 1 \]

• 如果字符不匹配，则取上方或左方的最大值：

\[ dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) \]

3. 计算 SCS 长度
   设 lcs_len = dp[len(s1)][len(s2)]，则最短公共超序列的长度为：

\[ \text{scs_len} = \text{len}(s1) + \text{len}(s2) - lcs_len \]

示例演示
以 s1 = "abac", s2 = "cab" 为例：

1. 构建 LCS 的 DP 表（见下表，行列索引 0 表示空串）：

       c a b  
     0 0 0 0  
   a 0 0 1 1  
   b 0 0 1 2  
   a 0 0 1 2  
   c 0 1 1 2  
   

   LCS 长度为 2（如 "ab" 或 "ac"）。
2. SCS 长度 = 4 + 3 - 2 = 5，与题目示例一致。

复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 为两字符串长度。
• 空间复杂度：可优化至 O(min(m, n))。