Levenshtein距离必须用二维DP，因其状态dpi依赖左、上、左上三个方向值（插入、删除、替换），一维数组会覆盖未使用的dpi-1导致错误；空间可优化至O(min(m,n))，通过滚动两行或单数组缓存topLeft实现，但需严格处理边界与状态更新顺序。
Levenshtein 距离为什么必须用二维 DP？
因为每一步编辑（插入、删除、替换）都依赖前一行和前一列的状态：dp[i][j] 表示 s1[0..i-1] 到 s2[0..j-1] 的最小编辑距离。标准写法需要 O(m×n) 空间，但实际计算第 i 行时，只用到第 i−1 行 —— 这就是空间可压缩的根本原因。
如何把二维 DP 压缩成两个一维数组？
只需维护当前行 curr 和上一行 prev，滚动更新即可：
vector<int> prev(n + 1), curr(n + 1);
for (int i = 0; i <ul>
<li>
<code>prev[j-1]</code> 对应「替换」，<code>prev[j]</code> 是「删除」，<code>curr[j-1]</code> 是「插入」</li>
<li>必须在内层循环开始前设 <code>curr[0] = i</code>，因为从空串变到 <code>s1[0..i−1]</code> 需 <code>i</code> 次插入</li>
<li>用 <code>swap()</code> 而非赋值，避免每次 <code>O(n)</code> 拷贝</li>
</ul>
<h3>还能进一步压到单数组吗？可以，但要小心覆盖顺序</h3>
<p>只用一个长度为 <code>n+1</code> 的数组 <code>dp</code>，但需缓存左上角旧值（即原 <code>prev[j-1]</code>）：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<pre class="brush:php;toolbar:false;">vector<int> dp(n + 1);
for (int j = 0; j <ul>
<li>关键点：每次迭代中，<code>topLeft</code> 必须在覆盖 <code>dp[j]</code> 前保存上一轮的 <code>dp[j]</code>（即原 <code>prev[j]</code>），它将在下一轮作为 <code>prev[j−1]</code>
</li>
<li>漏掉 <code>topLeft = top</code> 这句，就会用错左上角值，结果全错</li>
<li>单数组版省空间但可读性差，调试困难；生产环境建议优先用双数组版</li>
</ul>
<h3>边界与性能要注意什么？</h3>
<p>Levenshtein 计算本身不难，出问题多在细节：</p>
<ul>
<li>字符串索引从 0 开始，但 <code>dp[i][j]</code> 对应的是前 <code>i</code> 和前 <code>j</code> 个字符，务必检查 <code>s1[i-1]</code> / <code>s2[j-1]</code> 是否越界</li>
<li>若只关心是否 ≤ 某阈值（如拼写纠错），可用「带边界的编辑距离」（Ukkonens algorithm），提前终止，但标准 Levenshtein 不适用</li>
<li>
<code>min({a,b,c})</code> 是 C++11 起支持的初始化列表语法；老编译器需写成 <code>min(a, min(b, c))</code>
</li>
<li>对超长字符串（如 >50KB），即使空间优化后仍可能栈溢出 —— 改用 <code>new int[n+1]</code> 或 <code>std::vector</code> 在堆分配</li>
</ul>
<p>真正容易被忽略的，是 <code>topLeft</code> 的生命周期管理：它不是简单的临时变量，而是承载了跨两轮迭代的关键状态。少一次赋值，整个 DP 就崩了。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
