动态规划 · O(m×n) · 递推详解与逐步演示
X[0..m-1] 和 Y[0..n-1]，找出它们最长的公共子序列的长度。dp[i][j] = X[0..i-1] 和 Y[0..j-1] 的 LCS 长度。dp[0][j] = 0，dp[i][0] = 0，表示任意序列与空序列的 LCS 为 0）
dp[i][j] = dp[i-1][j-1] + 1 如果 X[i-1] == Y[j-1]（匹配） max(dp[i-1][j], dp[i][j-1]) 如果 X[i-1] != Y[j-1]（不匹配，取左/上较大者）
dp[0][*] = 0，dp[*][0] = 0（空序列与任何序列的 LCS 为 0）X[i-1] == Y[j-1]，则这个字符可以加入 LCS，dp[i][j] = dp[i-1][j-1] + 1X[i-1] != Y[j-1]，则 LCS 要么来自dp[i-1][j]），要么排除 Y[j-1]（左方 dp[i][j-1]），取较大值dp[m][n] 反向推演得到i = 1..m、j = 1..n 各计算一次 → O(mn)O(mn)（可优化为 O(min(m,n))，但回溯需要完整表时仍需 O(mn)）
#include <string> #include <vector> #include <algorithm> using namespace std; // 返回 LCS 的长度和序列 pair<int, string> longestCommonSubsequence(string X, string Y) { int m = X.size(), n = Y.size(); // dp[i][j]: X[0..i-1] 与 Y[0..j-1] 的 LCS 长度 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 填 DP 表 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (X[i - 1] == Y[j - 1]) { // 字符匹配，对角线 + 1 dp[i][j] = dp[i - 1][j - 1] + 1; } else { // 不匹配，取上方或左方的较大值 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } int len = dp[m][n]; // LCS 长度 // 回溯: 从 dp[m][n] 反向推演出 LCS 序列 string lcs; int i = m, j = n; while (i > 0 && j > 0) { if (X[i - 1] == Y[j - 1]) { // 匹配 → 加入 LCS，沿对角线移动 lcs.push_back(X[i - 1]); i--; j--; } else if (dp[i - 1][j] >= dp[i][j - 1]) { i--; // 上方更大 → 向上 } else { j--; // 左方更大 → 向左 } } reverse(lcs.begin(), lcs.end()); // 逆序得到正序 return {len, lcs}; }