C++最长公共子序列LCS怎么还原具体路径字符串-C++-PHP中文网

必须用directioni记录转移方向：0（左上匹配）、1（来自上方）、2（来自左方）；回溯时遇0则添加s1[i-1]并i,j均减1，否则按方向移动；因逆序构造，最终需反转字符串。

c++最长公共子序列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]，二者等价）加入结果——这个字符是当前子序列的末尾，但实际是最早被确定的“最后一个字符”。所以所有字符都是倒着加进去的。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

如果用 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]

dp[i][j] 值相同时，来自上方和左方的转移都合法，此时路径不唯一。比如 s1 = "ab", s2 = "ac"，LCS 长度为 1，但可以是 "a"（唯一），而 s1 = "abc", s2 = "acb" 就有两个 LCS："ab" 和 "ac"。

标准空间优化（只用两行 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 或漏掉等号判断，回溯就会卡死或跳过字符。