levenshtein距离二维dp内存爆掉是因为需o(m×n)空间，而实际只需两行滚动数组优化至o(min(m,n))；通过交换prev/curr并正确初始化边界（dpi=i, dp0=j）即可。
Levenshtein距离的二维DP实现为什么内存爆了？
直接用 std::vector<:vector>></:vector> 开二维数组算 Levenshtein 距离，当字符串长度超 10⁴ 就容易 OOM 或栈溢出——因为需要 O(m×n) 空间。实际中很少真需要整个 DP 表，多数场景只关心最终距离值，或需回溯编辑路径时才保留部分行。
- 经典二维写法：
dp[i][j]表示s1.substr(0,i)到s2.substr(0,j)的最小编辑距离 - 递推式固定：
dp[i][j] = min({dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(s1[i-1]!=s2[j-1])}) - 关键观察：计算第
i行只依赖第i-1行，因此可用两个一维数组滚动更新
怎么用两行 vector 实现空间 O(min(m,n))？
把长串放后面、短串放前面，再只维护 prev 和 curr 两行，每轮交换指针即可。注意初始化和边界处理不能错，否则 dp[0][j] 或 dp[i][0] 会全为 0 导致结果偏小。
- 先确保
s1.size() ，否则交换参数，让第一维尽量小 -
prev[j]初始为j（空串转s2.substr(0,j)需 j 次插入） -
curr[0]每轮设为i（s1.substr(0,i)转空串需 i 次删除） - 内层循环从
j=1开始，避免越界访问prev[j-1]
int levenshtein(const std::string& s1, const std::string& s2) {
if (s1.size() > s2.size()) return levenshtein(s2, s1);
int m = s1.size(), n = s2.size();
std::vector<int> prev(n + 1), curr(n + 1);
for (int j = 0; j
<h3>想还原编辑操作序列？别存整张表，改用“路径压缩”</h3>
<p>如果不仅要距离，还要知道具体做了哪些 insert/replace/delete，存二维表确实直观，但空间仍是问题。更实用的做法是：只存最后一行（<code>prev</code>），在计算过程中同步记录每步的决策来源（比如用 <code>char op[i][j]</code> 存 'D'/'I'/'R'/'M'），但这又回到 O(m×n) 空间。折中方案是分治 + 回溯：用 Hirschberg 算法，在 O(min(m,n)) 空间内还原路径，但实现复杂度高，一般业务场景用不到。</p>
<ul>
<li>简单需求（如仅判断是否 ≤ 阈值）：提前终止，一旦某行所有值都 > 阈值，直接返回 false</li>
<li>调试时想看某次替换位置：在 <code>cost==1</code> 且 <code>prev[j-1]+1 == curr[j]</code> 时记录 <code>i-1, j-1</code>
</li>
<li>注意：字符索引是 <code>i-1</code> 和 <code>j-1</code>，不是 <code>i</code>、<code>j</code> —— 这个 off-by-one 是最常导致 debug 半天的点</li>
</ul>
<h3>为什么用 int 而不用 unsigned int？</h3>
<p>因为 <code>prev[j] + 1</code> 可能溢出：当字符串很长（比如 2×10⁹ 字符），<code>int</code> 虽然也可能溢，但 <code>unsigned int</code> 溢出后变成 0，会污染后续所有计算，导致距离突变为极小值。而有符号溢出是未定义行为，但现代编译器通常按补码处理，至少不会“优雅地变 0”。</p>
<ul>
<li>生产环境建议用 <code>size_t</code> 仅当确认长度 long long 更稳妥</li>
<li>比较操作如 <code>curr[j] > threshold</code> 中，若 <code>threshold</code> 是 <code>int</code>，<code>curr[j]</code> 是 <code>unsigned</code>，隐式转换可能引发意外（如负阈值被转成极大正数）</li>
<li>Clang/GCC 加 <code>-Wsign-compare</code> 能抓到这类隐患</li>
</ul>
实际用时，80% 场景只需要距离值，滚动数组够用；剩下 20% 要路径，得权衡是否值得引入 Hirschberg 或接受 O(m×n) 内存。别一上来就抄教科书二维实现——那不是优化，是给自己埋雷。</int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
