LCS二维DP数组开m+1因状态定义为s1[0..i-1]与s2[0..j-1]的LCS长度，i=0或j=0对应空前缀，初始化为0；若开m则边界判断繁琐易越界。

为什么 lcs 二维 DP 数组要开 [m+1][n+1]

因为状态定义是「s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列长度」，下标从 1 开始才方便初始化空前缀（即 i=0 或 j=0 时值为 0）。如果开成 [m][n]，就得反复判断边界，代码又臭又容易越界。

常见错误现象：std::out_of_range 或访问到未初始化内存，尤其在循环里写成 dp[i][j] = dp[i-1][j-1] + 1 却没保证 i>0 && j>0。

• 初始化所有 dp[0][*] 和 dp[*][0] 为 0
• 字符串索引和 DP 索引错一位：比较的是 s1[i-1] 和 s2[j-1]
• 不要用 vector>(m, vector(n)) 初始化后手动补第 0 行/列——直接开 m+1 和 n+1 更稳

std::string 构造 LCS 路径时为什么必须倒着推

DP 表只存长度，不存决策路径。正向遍历无法知道哪条分支导致了当前最大值——比如 dp[i][j] == dp[i-1][j] 和 dp[i][j] == dp[i][j-1] 都可能成立，但只有其中一个对应实际转移来源。

使用场景：需要返回具体子序列（不止长度），比如调试验证、后续处理。

• 从 dp[m][n] 开始，根据值的来源反向走：s1[i-1]==s2[j-1] 就加入字符并跳到 dp[i-1][j-1]；否则选更大的那个方向（dp[i-1][j] 或 dp[i][j-1]）
• 别忘了最后把结果 reverse()，因为是倒着收集的
• 如果只要长度，这步完全跳过——省掉 O(m+n) 时间和空间

空间优化成一维数组时，prev 和 curr 怎么换

二维 DP 中，dp[i][j] 只依赖上一行（i-1）和本行左边（j-1）。所以可以用两个一维数组滚动，甚至只用一个数组加一个变量保存左上角旧值。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

性能影响：空间从 O(m×n) 降到 O(min(m,n))；但可读性下降，调试困难。

• 推荐先写二维版调通，再改一维——别一上来就抠空间
• 若用单数组 dp[n+1]，需在覆盖前用变量 diag 记住 dp[j-1] 上轮的值（即 dp[i-1][j-1]）
• 注意内层循环必须从左到右（不能倒序），否则 dp[j-1] 已被更新，丢失原始值

遇到空字符串或超长输入时，std::vector 分配失败怎么办

当 m 和 n 接近 1e4，二维 vector 会尝试分配 1e8 个 int（约 400MB），可能触发 std::bad_alloc，尤其在嵌入式或限制内存环境。

兼容性影响：不是算法错，是工程约束。C++ 标准库不保证大块连续内存一定成功。

• 上线前加保护：if (m > 5000 || n > 5000) throw std::runtime_error("input too large");
• 改用 std::deque<:vector>> 或分块计算（牺牲一点常数时间）
• 更现实的做法：确认是否真需要完整 DP 表——有些题只要长度，且允许 O(n) 空间，就别硬扛二维

边界 case 比理论推导更容易暴露问题：比如两个字符串都为空、一个为空、含大量重复字符（导致很多 dp[i][j] == dp[i-1][j-1]），这些时候手 trace 两三步比看公式管用。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！