C++实现LCS最稳方式是二维DP填表，dpi表示s1[0..i-1]与s2[0..j-1]的LCS长度，避免越界判断；状态转移仅两种情况：字符相等时dpi=dpi-1+1，否则dpi=max(dpi-1, dpi)；还原字符串需逆向回溯并注意相等情况处理。
直接说结论：C++ 实现 LCS 不需要记忆化递归，用二维 dp[i][j] 数组填表最稳；但数组索引偏移和状态转移的边界处理，是 90% 人第一次写错的地方。
为什么 dp[i][j] 表示的是 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
因为用 i=0 或 j=0 表示空字符串时，状态转移更干净——避免反复判断下标越界。如果定义成 dp[i][j] 对应 s1[i] 和 s2[j]，就得额外写一堆 if (i == 0 || j == 0) 分支，反而增加出错概率。
实操建议：
- 申请
vector，其中> dp(m + 1, vector (n + 1)) m = s1.size(),n = s2.size() - 初始化全为 0：空串与任意串的 LCS 长度都是 0
- 遍历时
i从 1 到m，j从 1 到n，对应比较s1[i-1]和s2[j-1]
dp[i][j] 的状态转移怎么写才不出错
核心就两条规则，别加多余条件：
- 如果
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])
注意：不是 max(dp[i-1][j-1], ...)，也不是三者取最大——dp[i-1][j] 和 dp[i][j-1] 已经涵盖了所有以 i-1 或 j-1 结尾的子情况，再拉上 dp[i-1][j-1] 是冗余且错误的。
常见错误现象：ab 和 ac 返回 2（实际应为 1），往往就是这里多加了 dp[i-1][j-1] 导致重复计数。
如何从 dp 表还原出具体的 LCS 字符串
填完表只是得到长度，要构造实际子序列，得从 dp[m][n] 往回走——这是最容易漏掉的一步。
实操要点：
- 用栈或字符串前插（
res = c + res）避免翻转 - 当
s1[i-1] == s2[j-1]时，该字符一定在 LCS 中，i--,j-- - 否则看
dp[i-1][j]和dp[i][j-1]哪个更大：相等时任选一个方向即可（结果不唯一，但长度保证正确） - 只要
i > 0 && j > 0就继续，别漏掉i==0 || j==0的终止判断
性能提示：空间可优化到 O(min(m,n))，但还原字符串必须保留完整二维表，否则路径信息丢失。
真正卡住人的从来不是状态定义，而是填表时下标错一位、回溯时没处理好相等情况、或者把「等于」分支写成「包含」逻辑。LCS 看似简单，但每个 -1 和每个 max 的取舍，都得对齐语义——少一次验证，就多一个隐藏 bug。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
