c++实现lcs最稳方式是二维dp填表，dpi表示s1[0..i-1]与s2[0..j-1]的lcs长度；需开(m+1)×(n+1)数组、i/j从1开始遍历、比较s1[i-1]和s2[j-1]，否则易越界或逻辑错误。
为什么直接用 std::string 做 LCS 动态规划时下标容易越界
因为 LCS 的 DP 表通常定义为 dp[i][j] 表示 s1.substr(0, i) 和 s2.substr(0, j) 的最长公共子序列长度，但很多人误把 i 当成字符串索引（0-based），实际它代表「前 i 个字符」，所以 DP 数组维度应为 (m+1) × (n+1)。若开成 m × n，访问 dp[i][j] 时在边界处（如 i == 0 或 j == 0）会读写非法内存，尤其开启 ASan 时直接报 heap-buffer-overflow。
实操建议：
- 初始化二维 vector：用
vector<vector>>(m + 1, vector<int>(n + 1, 0))</int></vector>，别省那个+1 - 遍历时
i从1到m（含），j从1到n（含），对应比较s1[i-1]和s2[j-1] - 不要手写裸数组（如
int dp[1000][1000]），除非确定长度上限且不传参；优先用vector避免栈溢出
如何从 DP 表反推 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，不是i == 1 || j == 1
示例片段（构造字符串）：
string lcs_str = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1[i-1] == s2[j-1]) {
lcs_str += s1[i-1]; // 注意：这是倒序添加
i--; j--;
} else if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
reverse(lcs_str.begin(), lcs_str.end()); // 最后翻转
空间优化到 O(min(m,n)) 是否影响路径重构
能压到 O(n) 空间（滚动数组），但代价是无法直接重构 LCS 字符串——因为丢掉了中间行/列的完整状态。如果只要长度，没问题；如果要字符串，要么放弃优化，要么改用分治法（Hirschberg 算法），但后者实现复杂、常数大，一般场景不值得。
权衡建议：
- 输入长度 ≤ 5000：直接用
O(m×n)空间，代码清晰不易错 - 输入长度 ≥ 10⁵：考虑用后缀自动机或 SAM + LCA（适合多查询），而非单次 LCS
- 真要空间敏感且必须输出字符串？接受
O(m×n)时间但用vector<vector>></vector>节省内存（长度不会超 32767）
遇到空字符串或中文字符时要注意什么
std::string 存的是字节，不是字符。若字符串含 UTF-8 中文，s[i] 取到的是单个字节，比较 s1[i-1] == s2[j-1] 会失败——因为一个汉字占 3 字节，而你在比其中某一个字节。
解决方向取决于需求：
- 若业务明确只处理 ASCII（如协议字段、文件名），无需额外处理
- 若需真正按 Unicode 字符比对，必须先将
std::string转为std::u32string（或std::vector<char32_t></char32_t>），用 ICU 或std::from_bytes（C++20）解析 UTF-8 - 切勿用
s1.substr(i-1, 1) == s2.substr(j-1, 1)来绕过——substr 在 UTF-8 中仍按字节截，可能截断汉字
边界最易被忽略的一点：空字符串参与计算时，dp[0][j] 和 dp[i][0] 必须全为 0，且循环变量起始值不能错设为 0 —— 这里错一点，整个表就全偏了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
