在C/C++中，最长公共子序列（Longest Common Subsequence, LCS）问题是一个经典的动态规划问题。它用于寻找两个序列中最长的公共子序列，而不是要求子序列在原序列中是连续的。LCS 算法在生物信息学（比如基因序列比对）、版本控制系统等领域有广泛的应用。

算法简介

最长公共子序列问题的基本思想是使用动态规划来记录和更新部分解，以便构建最终解。动态规划表通常是一个二维数组dp，其中dp[i][j]表示第一个序列的前i个字符和第二个序列的前j个字符之间的最长公共子序列的长度。

动态规划步骤

1. 状态表达式：

   • 若最后一个字符相同，dp[i][j] = dp[i-1][j-1] + 1
   • 若最后一个字符不同，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2. 边界条件：

   • 如果任何一个字符串长度为0，那么dp[i][0]或dp[0][j]都是0，因为空字符串和任何字符串的公共子序列长度为0。

3. 实现步骤：

   • 初始化表格dp为0。
   • 遍历两个字符串，更新dp表。
   • dp[m][n]的值即是所求的最长公共子序列长度，其中m和n是两个序列的长度。

策略实现

下面是一个 C++ 实现示例：

#include <iostream>  
#include <vector>  
#include <string>  
int longestCommonSubsequence(const std::string &text1, const std::string &text2) {  
    int m = text1.size();  
    int n = text2.size();  
    // 创建一个二维数组 dp  
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));  
    // 填充 dp 表  
    for (int i = 1; i <= m; ++i) {  
        for (int j = 1; j <= n; ++j) {  
            if (text1[i - 1] == text2[j - 1]) {  
                dp[i][j] = dp[i - 1][j - 1] + 1;  
            } else {  
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);  
            }  
        }  
    }  
    // dp[m][n] 是最终的结果  
    return dp[m][n];  
}  
int main() {  
    std::string text1 = "abcde";  
    std::string text2 = "ace";  
    int lcs_length = longestCommonSubsequence(text1, text2);  
    std::cout << "Longest Common Subsequence Length: " << lcs_length << std::endl;  
    return 0;  
}  

复杂性分析

• 时间复杂度：O(m * n)，其中m和n分别是两个输入字符串的长度。
• 空间复杂度：O(m * n)，用于存储动态规划表。如果只需要长度的话，可以优化到O(min(m, n))来进行空间优化。

通过这种方式，我们不仅可以获取最长公共子序列的长度，也可以通过回溯得出具体的子序列。这个问题的解法展示了动态规划在解决组合优化问题中的重要性。