必须用directioni记录转移方向：0（左上匹配）、1（来自上方）、2（来自左方）；回溯时遇0则添加s1[i-1]并i,j均减1，否则按方向移动；因逆序构造，最终需反转字符串。
怎么从LCS动态规划表里反推路径字符串
不能只存 dp[i][j] 的数值，必须同步记录决策来源。LCS 的状态转移有三种可能：dp[i-1][j]（删掉 s1[i-1]）、dp[i][j-1]（删掉 s2[j-1]）、dp[i-1][j-1] + 1（匹配成功）。还原路径的关键，是知道每一步选了哪条分支。
常见错误是：只用二维 int 数组算长度，没留空间记方向，导致最后完全无法回溯。
- 推荐在 DP 过程中维护一个同尺寸的
direction[i][j]矩阵，值为0（来自上）、1（来自左）、2（来自左上+匹配） - 初始化时，第一行/列全设为对应方向（比如
direction[0][j] = 1，因为只能从左来） - 匹配时（
s1[i-1] == s2[j-1]），必须设为2；不匹配时，比较dp[i-1][j]和dp[i][j-1]，取大者对应的方向；相等时可任选其一（通常选0或1都行，但要固定，否则路径不唯一）
还原路径时为什么字符串要逆序拼接
回溯是从 dp[m][n] 往 dp[0][0] 走，每次匹配成功（direction[i][j] == 2）时，把 s1[i-1]（或 s2[j-1]，二者等价）加入结果——这个字符是当前子序列的末尾，但实际是最早被确定的“最后一个字符”。所以所有字符都是倒着加进去的。
- 如果用
string res = ""然后res += s1[i-1]，最终得到的是反的，必须调用reverse(res.begin(), res.end()) - 更稳妥的做法是用
vector<char></char>收集，最后构造string，避免重复拷贝 - 注意下标：DP 表
dp[i][j]对应s1[0..i-1]和s2[0..j-1]，别越界访问s1[i]
当存在多个LCS时如何控制输出哪一条
dp[i][j] 值相同时，来自上方和左方的转移都合法，此时路径不唯一。比如 s1 = "ab", s2 = "ac"，LCS 长度为 1，但可以是 "a"（唯一），而 s1 = "abc", s2 = "acb" 就有两个 LCS："ab" 和 "ac"。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 只要在
dp[i-1][j] == dp[i][j-1]时统一优先选某个方向（如总是选0（来自上）），就能稳定输出其中一条 - 若想枚举所有 LCS，需改用 DFS + 记忆化，或 DP 表存储集合（代价高，一般不实用）
- 实际业务中，通常只需任意一条，优先选左或上对结果影响不大，但代码必须明确写死逻辑，不能靠
else if顺序隐式决定
边界与内存优化下的路径还原还能做吗
标准空间优化（只用两行 dp[2][n+1]）会丢掉中间决策信息，无法还原路径。哪怕你把 direction 也压成两行，仍然无法重建完整路径，因为缺少上上层的依赖关系。
- 只要需要还原具体字符串，就必须保留完整的
dp[m+1][n+1]和direction[m+1][n+1]表——空间复杂度O(mn)不可省 - 如果
m和n极大（如 > 10⁴），考虑用 Hirschberg 算法（空间O(min(m,n))），但它只支持还原一条 LCS，且实现复杂，需递归分治 + 两次正向扫描 - 日常使用中，别为了省几 MB 内存牺牲可调试性；路径还原本身就意味着你要看中间过程，压缩反而增加排查成本
真正容易被忽略的，是 direction 数组的初始化细节和匹配分支的强制覆盖逻辑——少写一行 else if 或漏掉等号判断，回溯就会卡死或跳过字符。
