LCS = 从两个序列里找「双方都有的、顺序一致」的最长子序列：在 A 里按顺序能挑出来，在 B 里按顺序也能挑出来。这是二维 DP（第 03 课的填表）第一次上大舞台：dp[i][j] 管「A 的前 i 个 与 B 的前 j 个」。
两个朋友各写了一份「周末想去的地方」清单，顺序是他们自己的优先级。你想找一份双方都同意、且各自顺序不变的最长共同清单——可以跳过不想去的地方，但不能把顺序打乱。这就是 LCS（Longest Common Subsequence，最长公共子序列）。LIS 是「一个序列里挑上升的」，LCS 是「两个序列里挑公共的」——所以表从一排变成一张二维表：行是 A 的前缀、列是 B 的前缀，dp[i][j] = 「A 前 i 个 与 B 前 j 个」的最长公共子序列长度。转移两条规则：① 末位相同——这对字符肯定能一起用（它们就是公共子序列的最后一对），dp[i][j] = dp[i-1][j-1] + 1；② 末位不同——A 的最后一个字符（或 B 的最后一个）进不了公共子序列，两种「删法」都试一下，取大的：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。边界：第 0 行、第 0 列 = 0（空序列的公共子序列长度为 0）。
// A = A B C B D A B（7 个字符，位置 1~7） // B = B D C A B （5 个字符，位置 1~5） // 公共子序列：在 A 里按顺序挑得出，且在 B 里也能按顺序挑得出 验证 "BCAB"： 在 A：B(2) C(3) A(6) B(7) → 位置 2,3,6,7 递增 ✓ 在 B：B(1) C(3) A(4) B(5) → 位置 1,3,4,5 递增 ✓ → "BCAB" 是公共子序列，长度 4 验证 "BDAB"： 在 A：B(2) D(5) A(6) B(7) → 2,5,6,7 ✓ 在 B：B(1) D(2) A(4) B(5) → 1,2,4,5 ✓ → 也是长度 4 验证 "ABCD"： 在 A：A(1) B(2) C(3) D(5) → ✓ 在 B：A(4) B(5) C(?) → C 在位置 3，在 A(4) 前面，顺序乱了 ✗ → "ABCD" 不是公共子序列（长度 4 存在，但这一条不行） // 问题：有长度 5 的公共子序列吗？——子任务 3 用 DP 一锤定音
// dp[i][j] = 「A 的前 i 个字符」与「B 的前 j 个字符」的 LCS 长度 // 边界：i = 0 或 j = 0（有一边是空串）→ LCS = 0 // 规则①：末位 A[i] 和 B[j] 相同 这一对字符可以作为公共子序列的最后一对： dp[i][j] = dp[i-1][j-1] + 1 （两边都去掉末位的答案 + 这一对字符） // 规则②：A[i] 和 B[j] 不同 它们配不成一对，LCS 里至少没有其中一个： · 删掉 A 的末位 → 答案 dp[i-1][j] · 删掉 B 的末位 → 答案 dp[i][j-1] dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // 小例子：LCS("AB", "BA") 全表 B A 0: 0 0 A: 0 1 A==A → dp[0][1]+1 = 1 B: 1 1 B==B → dp[1][0]+1 = 1； 中心格 A≠B → max(1, 1) = 1 → LCS("AB", "BA") = 1（「A」或「B」）
// 全表（边界行/列 = 0，逐行左到右填） B D C A B 0: 0 0 0 0 0 A: 0 0 0 1 1 B: 0 1 1 1 2 C: 0 1 1 2 2 B: 0 1 1 2 3 D: 0 1 2 2 3 A: 0 1 2 2 3 B: 0 1 2 2 3 4 ← 答案 dp[7][5] 验算 dp[7][5]：A[7]=B、B[5]=B 相同 → dp[6][4] + 1 = 3 + 1 = 4 ✓ 验算 dp[5][3]：D≠C → max(dp[4][3], dp[5][2]) = max(2, 2) = 2 ✓ // 倒推一条 LCS（从右下角 (7,5) 出发）： (7,5) B==B → 取 B，走 (6,4) (6,4) A==A → 取 A，走 (5,3) (5,3) D≠C → dp[4][3]=2 ≥ dp[5][2]=2 → 向上走 (4,3) (4,3) B≠C → dp[3][3]=2 ≥ dp[4][2]=1 → 向上走 (3,3) (3,3) C==C → 取 C，走 (2,2) (2,2) B≠D → dp[1][2]=0 < dp[2][1]=1 → 向左走 (2,1) (2,1) B==B → 取 B，走 (1,0) 结束 倒序收集：B A C B → 反转 → LCS = BCAB ✓（长度 4）
ans = A[i-1] + ans（每次插到最前面）就不用手动反转了。// 要点 1：字符串下标从 0 开始，dp 表从 1 开始 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1; // 对角 +1 else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // 要点 2：dp 开 [n+1][m+1]——第 0 行 / 第 0 列就是边界（全 0，int 默认 0） // 要点 3：倒推循环 while (i > 0 && j > 0) { if (A[i-1] == B[j-1]) { ans = A[i-1] + ans; i--; j--; } // 取字符走对角 else if (dp[i-1][j] >= dp[i][j-1]) i--; // 平手走上 else j--; }
A[i-1] 而不是 A[i]？② dp 为什么要开 [n+1][m+1]？③ 倒推循环为什么要 i > 0 && j > 0 才继续？A[i-1]。② 第 0 行 / 第 0 列要存「空串」的边界值，数组必须比 n、m 各多 1。③ i 或 j 到 0 就走到边界（空串），再走就数组越界了。// 题目：输入两个字符串 A、B，输出 LCS 长度和其中一条 LCS。 // 示例：输入 ABCBDAB / BDCAB → 长度 4，输出 BCAB #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string A, B; cin >> A >> B; int n = A.size(), m = B.size(); int dp[105][105] = {}; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; 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[n][m] << endl; // 倒推一条 LCS（每次把字符插到最前面，天然正序） string ans = ""; int i = n, j = m; while (i > 0 && j > 0) { if (A[i-1] == B[j-1]) { ans = A[i-1] + ans; i--; j--; } else if (dp[i-1][j] >= dp[i][j-1]) i--; else j--; } cout << "一条 LCS: " << ans << endl; return 0; } // 运行：输入 ABCBDAB / BDCAB // 输出：LCS 长度 = 4 // 一条 LCS: BCAB // 注意：LCS 可能有多条（BCAB、BDAB），程序输出其中一条即可。