【算法（四·三）：动态规划思想——最长公共子序列问题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法（四·三）：动态规划思想——最长公共子序列问题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法介绍

最长公共子序列（Longest Common Subsequence，简称LCS）问题是一种常见的字符串处理问题。它的**目标是找到两个或多个字符串中的最长公共子序列，这个子序列不需要是连续的，但字符在原始字符串中的相对顺序必须保持一致。**例如，考虑两个字符串"ABCD"和"ACDF"，它们的最长公共子序列是"ACD"。LCS问题通常在文本比对、版本控制、生物信息学（比如 DNA 序列比对）和自然语言处理等领域中有着广泛的应用。解决LCS问题通常采用动态规划算法。

形式化定义

最长公共子序列问题,算法,动态规划

问题分析

问题背景

最长公共子序列问题,算法,动态规划

枚举分析

枚举并检查长度为𝟏的子序列

… 长度为2、3的子序列同理
枚举并检查长度为𝟒的子序列
枚举并检查长度为5的子序列
长度为5的子序列没有，故长度为6的子序列就没有。
公共子序列如下
最长公共子序列如下

枚举观察

长度为n的子序列由长度为n-1的子序列组成。（其中n>=1）
最长公共子序列问题,算法,动态规划
故可能存在最优子结构和重叠子问题 因此要用动态规划思想求解。

算法步骤

问题结构分析
- 明确原始问题
  𝑪[𝒏, 𝒎]： 𝑿[𝟏. . 𝒏]和𝒀[𝟏. . 𝒎]的最长公共子序列长度
- 给出问题表示
  𝑪[𝒊,𝒋]：𝑿[𝟏. .𝒊]和𝒀[𝟏. .𝒋]的最长公共子序列长度
递推关系建立
- 分析最优（子）结构
  - 考察末尾字符
    - 情况𝟏：𝒙𝟕 ≠ 𝒚𝟔
      
      ①有2种情况，要么X的舍去一个后的结尾与Y结尾相同，要么Y的舍去一个后的结尾与X结尾相同。
      
      ②故有 $x_i!=y_j$ 时的关系
      
      ③故有 $x_i!=y_j$ 时的最优子结构
    - 情况2：𝒙𝟕 = 𝒚𝟔
      
      ①有3种情况，要么X、Y的结尾是公共子序列，要么X、Y结尾不是公共子序列（此时回到情况1的2种情况）
      
      ② 我们发现第一种情况包含了后两种i情况，因此后两种情况可以舍弃。
      
      ③故有 $x_i = y_i$ 之间的最优子结构
- 构造递推公式
自底向上计算
- 确定计算顺序
  - 状态初始化
    𝑪[𝒊,𝟎] = 𝑪[𝟎,𝒋] = 0 (某序列长度为0时，最长公共子序列长度为0。)
  - 明确子问题依赖关系
    由下列递推公式可知，𝑪[𝒊,j]依赖于𝑪[𝒊-1,j]、𝑪[𝒊,j-1]、𝑪[𝒊-1,j-1]
- 依次求解问题
  故计算顺序是“从左往右，从上到下”这样的自底向上计算。
最优方案追踪
- 构造追踪数组𝑹𝒆𝒄[𝟏. . 𝒏]，记录子问题来源。
  LU:代表左上方表格
  L：代表左侧表格
  U：代表上方表格
- 输出最长公共子序列