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 <= n; ++i) prev[i] = i;
for (int i = 1; i <= m; ++i) {
curr[0] = i;
for (int j = 1; j <= n; ++j) {
if (s1[i-1] == s2[j-1])
curr[j] = prev[j-1];
else
curr[j] = 1 + min({prev[j], curr[j-1], prev[j-1]});
}
prev.swap(curr); // 交换引用，避免拷贝
}
-
prev[j-1]对应「替换」，prev[j]是「删除」，curr[j-1]是「插入」 - 必须在内层循环开始前设
curr[0] = i，因为从空串变到s1[0..i−1]需i次插入 - 用
swap()而非赋值，避免每次O(n)拷贝
还能进一步压到单数组吗？可以，但要小心覆盖顺序
只用一个长度为 n+1 的数组 dp，但需缓存左上角旧值（即原 prev[j-1]）：
vector<int> dp(n + 1);
for (int j = 0; j <= n; ++j) dp[j] = j;
for (int i = 1; i <= m; ++i) {
int topLeft = dp[0]; // 保存 prev[j-1] 的初始值（即 prev[0]）
dp[0] = i;
for (int j = 1; j <= n; ++j) {
int top = dp[j]; // 相当于 prev[j]
int left = dp[j-1]; // 相当于 curr[j-1]
if (s1[i-1] == s2[j-1])
dp[j] = topLeft;
else
dp[j] = 1 + min({top, left, topLeft});
topLeft = top; // 更新 topLeft 为下一轮的 prev[j-1]
}
}
- 关键点：每次迭代中，
topLeft必须在覆盖dp[j]前保存上一轮的dp[j]（即原prev[j]），它将在下一轮作为prev[j−1] - 漏掉
topLeft = top这句，就会用错左上角值，结果全错 - 单数组版省空间但可读性差，调试困难；生产环境建议优先用双数组版
边界与性能要注意什么？
Levenshtein 计算本身不难，出问题多在细节：
立即学习“C++免费学习笔记（深入）”；
- 字符串索引从 0 开始，但
dp[i][j]对应的是前i和前j个字符，务必检查s1[i-1]/s2[j-1]是否越界 - 若只关心是否 ≤ 某阈值（如拼写纠错），可用「带边界的编辑距离」（Ukkonens algorithm），提前终止，但标准 Levenshtein 不适用
-
min({a,b,c})是 C++11 起支持的初始化列表语法；老编译器需写成min(a, min(b, c)) - 对超长字符串（如 >50KB），即使空间优化后仍可能栈溢出 —— 改用
new int[n+1]或std::vector在堆分配
真正容易被忽略的，是 topLeft 的生命周期管理：它不是简单的临时变量，而是承载了跨两轮迭代的关键状态。少一次赋值，整个 DP 就崩了。
