用一维滚动数组可将lcs长度计算优化至o(min(m,n))空间，核心是短串作列、从右往左更新并用prev保存左上状态，避免二维vector的内存不连续与缓存失效问题。
为什么 std::vector 二维 DP 表在 LCS 里容易拖慢速度？
因为标准二维 DP 需要 O(m*n) 空间和时间，而多数实际场景中字符串很长（比如 >10⁴），内存分配和缓存不友好会明显拖慢。更关键的是，std::vector<:vector>></:vector> 的每行内存不连续，CPU 预取失效，实测比一维滚动数组慢 2–3 倍。
- 优先用一维数组 + 临时变量滚动更新：
dp[j]表示当前行第j列，用prev记录左上角值 - 避免嵌套
vector：改用std::vector<int> dp(n + 1)</int>和一个int prev就够 - 如果只要长度不要路径，绝对不用二维表；如果要重构路径，再考虑空间换时间（如只存两行）
如何用滚动数组实现 O(min(m,n)) 空间 LCS 长度计算？
核心是把状态压缩到一行，并在每轮迭代中复用上一轮的“左上”信息。注意必须让短字符串做列方向，否则空间仍是大串长度。
- 设
s1为较短串（长度m），s2为较长串（长度n），申请std::vector<int> dp(m + 1)</int> - 遍历
s2每个字符时，从右往左更新dp[j]（避免覆盖还未用的dp[j-1]） - 用
prev保存上一轮dp[j-1]的值，即“左上角”状态
int lcs_length(const string& s1, const string& s2) {
if (s1.size() > s2.size()) return lcs_length(s2, s1);
int m = s1.size(), n = s2.size();
vector<int> dp(m + 1, 0);
for (int i = 0; i < n; ++i) {
int prev = 0; // dp[i-1][j-1]
for (int j = 1; j <= m; ++j) {
int tmp = dp[j];
if (s1[j-1] == s2[i]) dp[j] = prev + 1;
else dp[j] = max(dp[j], dp[j-1]);
prev = tmp;
}
}
return dp[m];
}
重构 LCS 字符串时，为什么不能直接用滚动数组？
滚动数组只保留最后一行状态，丢失了中间决策路径，无法回溯。强行记录所有行就回到 O(m*n) 空间 —— 这不是优化，是退化。
- 若必须返回子序列字符串，且内存允许，用两行数组：
prev_row和curr_row，只存最近两行 - 更省空间的做法：先算长度，再用分治 + 空间线性扫描（Hirschberg 算法），但实现复杂、常数大，仅当
n达 10⁶ 以上才值得 - 常见误操作：在滚动循环里保存
path向量——它会在每次内层循环被反复 push/pop，性能崩坏
std::string_view 能否加速 LCS 输入处理？
能，但只在传参和比较阶段省拷贝，不影响 DP 主循环。很多人以为用了 string_view 就自动变快，其实瓶颈永远在双重循环本身。
立即学习“C++免费学习笔记（深入）”；
- 函数签名建议写成
int lcs_length(string_view s1, string_view s2)，避免构造临时string - 内部仍要用
s1.data()或下标访问，string_view::at()有边界检查开销，别用 - 注意：如果输入来自
std::cin或文件流，先读进string再转string_view，别指望流直接给 view
