两种方法求解最长公共子序列问题并输出所有解

最长公共子序列（Longest Common Subsequence, LCS）是动态规划领域的经典问题，广泛应用于生物信息学（如DNA序列比对）、文本差异比对（如Git版本控制）等领域。本文将通过​​自顶向下递归+记忆化​​、​​自底向上动态规划​​以及​​回溯法找所有解​​三种方法，深入剖析LCS问题的求解过程，并提供完整的代码实现与实例验证

1.1 什么是LCS？

给定两个字符串text1和text2，其最长公共子序列定义为：在不改变字符相对顺序的前提下，两个字符串共有的最长字符序列。例如，text1=“abcde”，text2=“ace"的LCS为"ace”，长度为3。

1.2 动态规划的核心思想

动态规划通过​​分解问题​​、​​存储中间状态​​（即子问题的解）来避免重复计算。对于LCS问题，定义状态dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度。状态转移方程如下：

边界条件为dp[0][j]=0和dp[i][0]=0，即空字符串的LCS长度为0。

算法实现与优化

2.1 自顶向下递归+记忆化（Top-Down）

通过递归分解问题，并用二维数组memo存储已计算的子问题结果，避免重复计算。

int upToDown(string& a, string& b, int m, int n, vector<vector<int>>& memo) {
    if (m == 0 || n == 0) return 0;
    if (memo[m][n] != -1) return memo[m][n]; // 记忆化查询
    
    if (a[m-1] == b[n-1]) {
        memo[m][n] = 1 + upToDown(a, b, m-1, n-1, memo);
    } else {
        memo[m][n] = max(upToDown(a, b, m-1, n, memo), 
                        upToDown(a, b, m, n-1, memo));
    }
    return memo[m][n];
}

时间复杂度​​：O(mn)，​​空间复杂度​​：O(mn)。

2.2 自底向上动态规划（Bottom-Up）

通过迭代填充二维数组dp，从最小子问题逐步求解最终结果。

void downToUp(string a, string b) {
    int m = a.length(), n = b.length();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << "LCS长度：" << dp[m][n];
}

优势​​：无需递归栈，适合大规模输入。

回溯法找所有最优解

3.1 回溯原理

基于动态规划表dp，从dp[m][n]反向追踪所有可能的路径。当字符相等时向左上回溯，否则根据dp值选择向上或向左回溯。

void LCS_Backtrack(string& X, string& Y, vector<vector<int>>& dp, 
                   int i, int j, string current, vector<string>& result) {
    if (i == 0 || j == 0) {
        reverse(current.begin(), current.end());
        result.push_back(current);
        return;
    }
    
    if (X[i-1] == Y[j-1]) {
        current.push_back(X[i-1]);
        LCS_Backtrack(X, Y, dp, i-1, j-1, current, result);
        current.pop_back();
    } else {
        if (dp[i-1][j] == dp[i][j]) {
            LCS_Backtrack(X, Y, dp, i-1, j, current, result);
        }
        if (dp[i][j-1] == dp[i][j]) {
            LCS_Backtrack(X, Y, dp, i, j-1, current, result);
        }
    }
}

注意​​：由于回溯路径是从后向前构建，最终需要反转字符串。

测试案例 && 完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100;

// 自底向上
void downToUp(string a, string b) {
    int al = a.length();
    int bl = b.length();

    int D[N][N];
    for (int i = 1; i <= al; i++) {
        for (int j = 1; j <= bl; j++) {
            if (a[i - 1] == b[j - 1]) {
                D[i][j] = D[i - 1][j - 1] + 1;
            } else {
                D[i][j] = max(D[i - 1][j], D[i][j - 1]);
            }
        }
    }
    cout << "最长公共子序列长度: " << D[al][bl] << endl;
}

// 自上向下，传入的二维数组初始化为一
int upToDown(string& a, string& b, int m, int n, vector<vector<int>>& memo) {
    if (m == 0 || n == 0) return 0; // 递归终止条件
    if (memo[m][n] != -1) return memo[m][n]; // 计算过直接返回结果

    if (a[m - 1] == b[n - 1]) {
        memo[m][n] = 1 + upToDown(a, b, m - 1, n - 1, memo);
    } else {
        memo[m][n] = max(upToDown(a, b, m - 1, n, memo), upToDown(a, b, m, n - 1, memo));
    }

    return memo[m][n];
}

// 3. 回溯法找到所有最长公共子序列
void LCS_Backtrack(string& X, string& Y, vector<vector<int>>& dp, int m, int n, string& current, vector<string>& result) {
    // 如果到达矩阵的边界，表示一个公共子序列的结束
    if (m == 0 || n == 0) {
        result.push_back(current);  // 到达边界，记录一个解
        return;
    }

    // 如果当前字符相等，将字符加入当前子序列，回溯到左上角
    if (X[m - 1] == Y[n - 1]) {
        current.push_back(X[m - 1]);  // 字符匹配，添加到当前子序列
        LCS_Backtrack(X, Y, dp, m - 1, n - 1, current, result);
        current.pop_back();  // 回溯，移除字符
    } else {
        // 如果上方 dp 值等于当前 dp 值，说明从上面来的
        if (dp[m - 1][n] == dp[m][n]) {
            LCS_Backtrack(X, Y, dp, m - 1, n, current, result);  // 向上回溯
        }

        // 如果左边 dp 值等于当前 dp 值，说明从左边来的
        if (dp[m][n - 1] == dp[m][n]) {
            LCS_Backtrack(X, Y, dp, m, n - 1, current, result);  // 向左回溯
        }
    }
}

int main() {
    string a, b;
    cin >> a >> b;

    int m = a.length();
    int n = b.length();


    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];  
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  
            }
        }
    }

    vector<string> result;
    string current;
    LCS_Backtrack(a, b, dp, m, n, current, result);

    cout << "所有的最长公共子序列: " << endl;
    for (const auto& seq : result) {
    	string re = seq;
    	reverse(re.begin(), re.end());
        cout << re << endl;
    }

    return 0;
}

输入
ABCBDAB
BDCABC
输出
4
所有的最长公共子序列:
BCAB
BDAB

end