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

算法（四·三）：动态规划思想——最长公共子序列问题

• 算法介绍
• • 形式化定义
  • 问题分析
  • • 问题背景
    • 枚举分析
    • 枚举观察
    • 算法步骤
    • 算法实例
    • 算法伪代码
    • 算法性能
    • • 时间复杂度
      • 空间复杂度
      • 稳定性
      • 算法总结

        算法介绍

        最长公共子序列（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 xi​!=yj​时的关系

                    ③故有 x i ! = y j x_i!=y_j xi​!=yj​时的最优子结构

                  • 情况2：𝒙𝟕 = 𝒚𝟔

                    ①有3种情况，要么X、Y的结尾是公共子序列，要么X、Y结尾不是公共子序列（此时回到情况1的2种情况）

                    ② 我们发现第一种情况包含了后两种i情况，因此后两种情况可以舍弃。

                    ③故有 x i = y i x_i = y_i xi​=yi​之间的最优子结构

                  • 构造递推公式

                  • 自底向上计算

                    • 确定计算顺序

                      • 状态初始化

                        𝑪[𝒊,𝟎] = 𝑪[𝟎,𝒋] = 0 (某序列长度为0时，最长公共子序列长度为0。)

                      • 明确子问题依赖关系

                        由下列递推公式可知，𝑪[𝒊,j]依赖于𝑪[𝒊-1,j]、𝑪[𝒊,j-1]、𝑪[𝒊-1,j-1]

                      • 依次求解问题

                        故计算顺序是“从左往右，从上到下”这样的自底向上计算。

                      • 最优方案追踪

                        • 构造追踪数组𝑹𝒆𝒄[𝟏. . 𝒏]，记录子问题来源。

                          LU:代表左上方表格

                          L：代表左侧表格

                          U：代表上方表格

                        • 输出最长公共子序列

                          算法实例

                          • 填公共子序列长度与REC数组

                            … 以此类推

                            • 追溯序列

                              算法伪代码

                              算法性能

                              时间复杂度

                              该算法的时间复杂度是O(m * n)，其中m和n分别是两个输入字符串的长度。这是因为算法使用一个二维表格进行计算，需要填充m * n 个单元格，每个单元格的计算是常数时间操作。在实际应用中，该算法在处理相对较小的字符串时性能良好，但对于非常大的字符串，时间复杂度可能会成为性能瓶颈。

                              空间复杂度

                              空间复杂度主要取决于动态规划表格的大小，为O(m * n)。这意味着算法需要分配和维护一个大小为m * n的二维数组。对于大型输入字符串，这可能导致内存消耗较大。

                              稳定性

                              该算法是稳定的，即对于相同的输入，它始终产生相同的输出。这是因为它基于确定性的动态规划原理，不受随机性或不确定性的影响。

                              算法总结

                              总的来说，利用动态规划思想解决最长公共子序列问题方面具有较高的准确性和稳定性，但需要权衡时间复杂度和空间复杂度。在实际应用中，需要根据具体问题和输入规模来评估是否合适使用此算法。