最长公共子序列（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​之间的最优子结构

自底向上计算

确定计算顺序

依次求解问题 故计算顺序是“从左往右，从上到下”这样的自底向上计算。

最优方案追踪

… 以此类推

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

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

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

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