如何求解两个以上字符串的最长公共子序列（LCS）

双串LCS的动态规划思路可以直接拓展到多串场景，核心逻辑是把二维DP状态升维到和字符串数量匹配的维度，具体实现逻辑如下： #

核心DP状态定义 #

假设我们要计算k个字符串的LCS，每个串的长度分别为n₁, n₂, ..., n_k：

• 定义k维DP数组dp[i₁][i₂]...[i_k]，表示「第1个串取前i₁个字符、第2个串取前i₂个字符……第k个串取前i_k个字符」时，对应的最长公共子序列长度。

状态转移规则 #

和双串逻辑一致，分两种情况处理：

• 若当前所有串的指针位置字符完全相同（即s₁[i₁-1] == s₂[i₂-1] == ... == s_k[i_k-1]，这里DP下标从1开始预留空串边界，和字符串0开始的下标错位1位），说明这个公共字符可以加入LCS，状态转移为：

  dp[i₁][i₂]...[i_k] = dp[i₁-1][i₂-1]...[i_k-1] + 1
  

• 若当前位置的字符不完全一致，就枚举所有「将其中一个串的指针回退1位」的前驱状态，取所有前驱结果的最大值：

  dp[i₁][i₂]...[i_k] = max(
      dp[i₁-1][i₂][i₃]...[i_k],
      dp[i₁][i₂-1][i₃]...[i_k],
      ...,
      dp[i₁][i₂]...[i_k-1]
  )
  

边界处理 #

所有维度下标为0的状态值统一为0——也就是只要任意一个串取空前缀，公共子序列长度必然为0。

复杂度说明 #

这个基础DP方法的时间、空间复杂度都是各串长度的乘积，即O(n₁*n₂*...*n_k)。要注意k个串的LCS问题本身是NP-hard问题，不存在随k增长的多项式时间通用解法，所以这个DP方法只适合串数量少（一般k≤5）、单串长度不大的场景。如果输入规模更大，可以根据需求选择近似算法优化。

补充：还原具体LCS序列 #

如果需要拿到具体的公共子序列内容而不只是长度，和双串LCS的回溯逻辑完全一致：从最终状态dp[n₁][n₂]...[n_k]反向遍历：

• 如果当前状态是由「所有指针回退1位+1」转移来的，说明当前位置的公共字符属于LCS，记录该字符后往全退1的状态走
• 否则往值和当前状态相等的任意一个前驱状态（单指针回退1位的状态）移动即可，直到走到边界就得到反向的LCS，反转后就是结果。

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