字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列
【最长公共子序列】(Longest Common Subsequence, LCS) 是一种在计算机科学中常见的字符串比较问题，主要涉及序列和动态规划。这个问题的目标是找到两个给定字符串的最长子序列，这个子序列不必连续，但必须保持原序列的相对顺序。
在给定的描述中，我们有两个字符序列 X 和 Y，它们的最长公共子序列（LCS）定义为从 X 中删除若干字符（可能不删除）得到的序列，这个序列同时也是 Y 的子序列。例如，X="ABCBDAB"，Y="BCDB"，则 "BCD" 是它们的 LCS。
动态规划方法是解决此类问题的有效工具。基本思想是将大问题分解成一系列子问题，并存储每个子问题的解，以避免重复计算。在 LCS 问题中，我们使用一个二维数组 c[][] 来存储 X[i] 与 Y[j] 的 LCS 长度。另一个二维数组 b[][] 用于记录 c[i][j] 是如何得出的，帮助回溯找到实际的 LCS。
对于状态转移方程，我们可以根据 X[i] 和 Y[j] 是否相等来确定 c[i][j]。如果它们相等，那么 c[i][j] = c[i-1][j-1] + 1；如果不相等，我们将选择 c[i-1][j] 和 c[i][j-1] 中较大的那个作为 c[i][j] 的值。这可以通过比较 X[i-1] 和 Y[j-1] 来实现。
以下是使用 C 语言实现的动态规划求解 LCS 的伪代码：
```c
void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) {
for (i = 0; i <= m; i++)
c[i][0] = 0;
for (j = 1; j <= n; j++)
c[0][j] = 0;
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
if (x[i-1] == y[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 0;
} else if (c[i-1][j] >= c[i][j-1]) {
c[i][j] = c[i-1][j];
b[i][j] = 1;
} else {
c[i][j] = c[i][j-1];
b[i][j] = 2;
}
}
}
}
```
算法的时间复杂度为 O(m * n)，其中 m 和 n 分别是两个输入序列的长度。这是因为我们需要遍历两个序列的所有可能对，每个操作的时间复杂度为 O(1)。空间复杂度也是 O(m * n)，因为需要存储整个二维数组。
回溯 b[][] 数组可以构造出实际的 LCS。从 c[m][n] 开始，根据 b[i][j] 的值判断是往左还是往上回溯，直到 i=0 或 j=0，这样就得到了最长公共子序列。
总结来说，最长公共子序列问题是一种经典的动态规划问题，通过构建二维数组来存储子问题的解，有效地避免了重复计算，提高了求解效率。此问题在生物信息学、文本比较、代码编辑器的差异计算等领域有广泛的应用。
