levenshtein距离二维dp内存易爆因空间复杂度o(m×n)，如10⁴×10⁴数组导致bad_alloc；实际只需两行滚动数组，用prev和curr代替整表，每次仅依赖上一行与左邻，空间降至o(n)。
Levenshtein距离的二维DP解法为什么内存容易爆？
直接用 dp[i][j] 表示 s1[0..i-1] 到 s2[0..j-1] 的最小编辑距离，空间复杂度是 O(m*n)。当字符串长度超 10⁴，比如处理日志或 DNA 序列时，分配一个 10000×10000 的 int 数组会直接触发 std::bad_alloc 或栈溢出（若在栈上声明）。
关键原因不是计算慢，而是中间状态全保留——而每次更新 dp[i][j] 只依赖上一行和左邻：即 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]。这意味着整张表根本不需要存下来。
只用两行数组实现空间优化的要点
把二维降为一维滚动数组，实际只需两个长度为 n+1 的 vector<int></int>：prev 和 curr，分别对应上一行和当前行。
-
prev[j]对应原dp[i-1][j]，curr[j-1]对应dp[i][j-1]，prev[j-1]对应dp[i-1][j-1] - 初始化
prev[j] = j（空串到s2[0..j-1]需 j 次插入），curr[0] = i（s1[0..i-1]到空串需 i 次删除） - 内层循环从
j = 1开始，避免越界；字符相等时curr[j] = prev[j-1]，否则取三者最小值加 1 - 每轮结束前执行
swap(prev, curr)或prev = curr，为下一轮准备
边界处理与字符索引易错点
Levenshtein 的 DP 状态定义必须对齐“前 i 个字符”，而非下标 i。常见错误是把 s1[i] 和 s2[j] 直接比较，却忘了 dp[i][j] 描述的是 s1[0..i-1] 和 s2[0..j-1] —— 这会导致越界或逻辑偏移 1。
- 输入字符串
s1 = "ab",s2 = "a"，正确距离是 1（删 'b'），但若误用s1[i] == s2[j]且 i/j 从 0 开始，会在i=1,j=0时比较'b'和'a'，跳过首字符匹配 - 务必确保循环变量
i范围是[1, m]，j是[1, n]，访问字符用s1[i-1]和s2[j-1] - 若用
string::at()，它抛异常；用[]则静默越界——调试时建议先断言i-1
要不要进一步压缩到单数组？
可以，但代价是引入临时变量保存“左上角”值。单数组方案用 vector<int> dp(n+1)</int>，并维护一个 diag 变量记录上一轮的 dp[j-1]（即原 dp[i-1][j-1]）。
- 初始化
dp[j] = j；外层i从 1 到 m，先存dp[0]到temp（即旧的dp[0]，代表dp[i-1][0]），然后设dp[0] = i - 内层
j从 1 到 n：先用diag（即上轮dp[j-1]）、dp[j]（上轮dp[j]）、dp[j-1]（本轮刚更新的左值）算新值，再更新diag = temp，temp = dp[j] - 单数组省空间，但可读性下降，且现代 CPU 缓存对两行数组友好，实际性能差异常不明显；除非内存极端受限，否则推荐两行写法
真正难的不是推导公式，而是确认你比较的到底是哪两个子串、下标有没有多减一次、初始化有没有漏掉空串情况——这些地方错一点，结果就全偏了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
