动态规划之最长公共子序列

---

1. 问题描述

​ 若给定序列\(X = {x_1, x_2,\ldots,x_m}\)，则另一序列 \(Z = {z_1, z_2, \ldots,z_k}\)是\(X\)的子序列，是指存在一个严格递增下标序列\({i_1,i_2,\ldots,i_k}\)，使得对于所有\(j = 1, 2,\ldots,k\)，有：\(z_j = x_{i_j}\)。如：序列\(Z = {B, C, D, B}\)是序列\(X = {A, B, C, B, D, A, B}\)的子序列，相应的递增下标序列为\({2, 3, 5, 7}\)。
​ 给定2个序列\(X\)和\(Y\)，当另一序列\(Z\)既是\(X\)的子序列又是\(Y\)的子序列时，称\(Z\)是序列\(X\)和\(Y\)的公共子序列。
​ 给定2个序列\(X = {x_1, x_2,\ldots,x_m}\)和\(Y = {y_1, y_2,\ldots,y_n}\)，找\(X\)，\(Y\)的最长公共子序列。

2. 问题分析

2.1 最优解(最长公共子序列)的结构

​ 设序列\(X = {x_1, x_2,\ldots,x_m}\)和\(Y = {y_1, y_2,\ldots,y_n}\)的最长公共子序列为\(Z = {z_1, z_2, \ldots,z_k}\)，则：
​ ① 若\(x_m = y_n\)，则\(z_k = x_m = y_n\)，且\(Z - z_k\)是\(X - x_m\)和\(Y - y_n\)的最长公共子序列。
​ ② 若\(x_m \neq y_n\)且\(z_k \neq x_m\)，则\(Z\)是\(X - x_m\)和\(Y\)的最长公共子序列。
​ ③ 若\(x_m \neq y_n\)且\(z_k \neq y_n\)，则\(Z\)是\(X\)和\(Y - y_n\)的最长公共子序列。
​ 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质

2.2最优值的递归定义

​ 用\(c[i][j]\)记录序列的最长公共子序列的长度。其中\(X_i= {x_1, x_2,\ldots, x_i}\);\(Y_j= {y_1, y_2,\ldots, y_j}\)。递归关系如下：

\[c[i][j] = \begin{cases} 0 &\text i = 0 \bigvee j = 0 \\ c[i - 1][j - 1] + 1 &\text i, j > 0; x_i = y_j \\ max\{c[i][j - 1], c[i - 1][j]\} &\text i, j > 0; x_i \neq y_j \end{cases} \]

2.3计算最优值

​ 二维表b是辅助构造最优解的信息表：
​ 当\(b[i][j] = 1\)时，则表示\(c[i][j] = c[i - 1][j - 1] + 1\);
​ 当\(b[i][j] = 2\)时，则表示\(c[i][j] = c[i - 1][j]\);
​ 当\(b[i][j] = 3\)时，则表示\(c[i][j] = c[i][j - 1]\);

/**
 * m 序列X的长度
 * n 序列Y的长度
 * x 序列X
 * y 序列Y
 * c 存储最优解c[i][j]的值
 * b 辅助信息，用于构造最优解
 **/
void LCSLength(int m, int n, char *x, char *y, int **c, int **b) {
    int i, j;
    // 俩个序列有一个为空，则最长子序列也为空
    for (i = 1; i <= m; i++)
        c[i][0] = 0;
    for (i = 1; i <= n; i++)
        c[0][i] = 0;
    // 遍历两个序列，计算序列比较的所有情况
    for (i = 1; i<= m; i++)
        for (j = 1; j <= n; j++) {
            // 按照递推式，计算所有的情况
            if (x[i] == y[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1;
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 2;
            } else {
                c[i][j] = c[i][j - 1];
                b[i][j] = 3;
            }
        }
}

2.4构造最优解

// 递归输出最优解结构
void LCS(int i, int j, char *x, int **b) {
    if (i == 0 || j == 0)
        return ;
    if (b[i][j] == 1) {
        LCS(i - 1, j - 1, x, b);
        printf("%c", x[i]);
    } else if (b[i][j] == 2)
        LCS(i - 1, j, x, b);
    else
        LCS(i, j - 1, x, b);
}