用动态规划法求解最长公共子序列问题 【问题描述】字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。 令给定的字符序列X=（x0，x1，…，xm-1），序列Y=（y0，y1，…，yk-1）是X的子序列，存在X的一个严格递增下标序列（i0，i1，…，ik-1），使得对所有的j=0，1，…，k-1，有 x_(i_j )=y_j 子序列:例如，X=（a，b，c，b，d，a，b），Y=（b，c，d，b）是X的一个子序列。 给定两个字符序列A和B，如果字符序列Z既是A的子序列，又是B的子序列，则称序列Z是A和B的公共子序列。该问题是求两序列A和B的最长公共子序列（LCS）。 例如，X=（a，b，c，b，d，b），m=6，Y=（a，c，b，b，a，b，d，b，b），n=9。求序列X和序列Y的最长公共子序列LCS。（结果LCS="acbdb"）

### 动态规划法求解最长公共子序列问题 动态规划是一种高效解决问题的技术，尤其适用于具有重叠子问题和最优子结构性质的问题。对于最长公共子序列（Longest Common Subsequence, LCS）问题，可以通过动态规划方法将其分解为多个较小的子问题并有效解决。 #### 1. 定义状态 设两个字符串分别为 `X` 和 `Y`，长度分别为 `m` 和 `n`。定义二维数组 `dp[i][j]` 表示字符串 `X[0..i-1]` 和 `Y[0..j-1]` 的最长公共子序列的长度[^1]。 #### 2. 转移方程 根据字符匹配情况，转移方程可以表示如下： - 如果 `X[i-1] == Y[j-1]`，则有： \[ dp[i][j] = dp[i-1][j-1] + 1 \] - 否则，取两者中的较大值： \[ dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) \] 此过程体现了动态规划的核心思想，即将大问题拆分为若干个小问题，并通过已知的小问题结果推导出最终答案[^2]。 #### 3. 边界条件 初始化边界条件时需要注意： - 当任意一个字符串为空时，其与另一个字符串的最长公共子序列为零，因此设置初始值为： \[ dp[i][0] = 0,\quad dp[0][j] = 0 \] #### 4. 构造最优解 在完成动态规划表填充后，可以从右下角回溯到左上角，找到具体的最长公共子序列。具体做法是从 `dp[m][n]` 开始，按照以下规则反向追踪路径： - 若 `X[i-1] == Y[j-1]`，说明该字符属于公共子序列； - 否则比较 `dp[i-1][j]` 和 `dp[i][j-1]` 的大小，决定移动方向。 以下是完整的 C 实现代码： ```c #include <stdio.h> #include <string.h> void lcs(char *X, char *Y, int m, int n) { int dp[m+1][n+1]; // 填充 DP 数组 for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) dp[i][j] = 0; else if (X[i-1] == Y[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1]; } } // 输出最长公共子序列 int index = dp[m][n]; char lcs[index+1]; // 存储结果 lcs[index] = '\0'; int i = m, j = n; while (i > 0 && j > 0) { if (X[i-1] == Y[j-1]) { lcs[index-1] = X[i-1]; i--; j--; index--; } else if (dp[i-1][j] > dp[i][j-1]) i--; else j--; } printf("The Longest Common Subsequence is \"%s\"\n", lcs); } int main() { char X[] = "AGGTAB"; char Y[] = "GXTXAYB"; int m = strlen(X); int n = strlen(Y); lcs(X, Y, m, n); return 0; } ``` 以上程序实现了基于动态规划的最长公共子序列算法，并打印出了对应的子序列[^3]。