c++实现lcs最稳方式是二维dp填表，dpi表示s1[0..i-1]与s2[0..j-1]的lcs长度；初始化dp0=dpi=0，状态转移为：字符相等时dpi=dpi-1+1，否则dpi=max(dpi-1, dpi)；还原字符串需从dpm逆向回溯并反转结果。
为什么直接递归会超时
因为 lcs 问题存在大量重复子问题：比如计算 lcs("abcde", "abfde") 时，lcs("bcd", "bfde") 和 lcs("bcde", "bde") 都会再次调用 lcs("cd", "bde")。纯递归时间复杂度是 O(2^(m+n))，字符串稍长（比如长度 > 30）就卡死。
必须用记忆化或 DP 表避免重复计算。推荐从二维 DP 入手，更直观也更容易调试。
二维 DP 数组怎么初始化和填表
设 s1 长度为 m，s2 长度为 n，定义 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列长度。
-
dp[0][j] = 0（空串和任意串的 LCS 长度为 0） -
dp[i][0] = 0（同理） - 当
s1[i-1] == s2[j-1]时：dp[i][j] = dp[i-1][j-1] + 1 - 否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
注意下标偏移 —— dp 是 1-based 语义，但数组索引是 0-based，别把 s1[i] 和 dp[i][j] 的 i 混用。
如何还原具体的 LCS 字符串
DP 表只存长度，要构造实际子序列得回溯。从 dp[m][n] 出发往左上走：
- 若
s1[i-1] == s2[j-1]，该字符属于 LCS，加入结果，然后向dp[i-1][j-1]移动 - 否则，比较
dp[i-1][j]和dp[i][j-1]：选大的方向走（相等任选其一即可） - 回溯完后把结果反转，才是正序 LCS
常见错误是忘记反转，或者在相等时没处理好边界（比如 i==0 或 j==0 时不能继续访问 dp[i-1][j-1]）。
空间优化到 O(min(m,n)) 可行吗
可以，但仅适用于求长度，不适用于还原字符串。因为滚动数组只保留两行，丢掉了中间状态，无法回溯。
如果只要长度，用 vector<int> prev(n+1), curr(n+1)</int> 就够了；如果还要输出子序列，必须保留完整二维表，或额外记录路径（比如用 vector<vector>></vector> 存决策方向），空间仍是 O(m*n)。
别为了省几 MB 内存牺牲可调试性 —— 实际项目里，LCS 输入一般不会大到爆内存，先写清楚逻辑，再看是否真需要优化。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
