Levenshtein距离二维DP空间浪费严重是因为仅需上一行和左邻格，却分配O(m×n)内存；可优化为O(min(m,n))一维滚动数组，用prev和temp维护左上角值，从左到右更新。
Levenshtein 距离的二维 DP 实现为什么空间浪费严重
标准 Levenshtein 动态规划用 dp[i][j] 表示 s1[0..i-1] 到 s2[0..j-1] 的编辑距离，需要 O(m×n) 空间。但每次只依赖上一行和左邻格（dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]），整张表绝大多数格子在计算完当前行后就再无用途。
实际项目中若处理长字符串（如 10k 字符以上），分配二维 vector 可能触发内存分配失败或显著拖慢——尤其在嵌入式或高频调用场景下。
- 典型错误：直接写
vector<vector>> dp(m+1, vector<int>(n+1))</int></vector>，没意识到n是动态变量，可能远超预期 - 更隐蔽的问题：编译器对二维 vector 的 cache 局部性差，访问
dp[i][j]时容易 cache miss - 优化方向不是“省几 KB”，而是把空间从
O(m×n)压到O(min(m,n))
如何用一维数组滚动更新实现正确 DP
核心是复用单行数组，用两个临时变量保存“左上角”值（即 dp[i-1][j-1]）。关键在于更新顺序必须从左到右，且每次覆盖前先缓存旧值。
以 s1 为行、s2 为列为例，设 dp[j] 表示当前行第 j 列结果。进入第 i 行前，dp[j] 存的是上一行的值；计算新值时需：
立即学习“C++免费学习笔记（深入）”；
- 用变量
prev记录dp[j-1]（即左上角）在被覆盖前的值 - 用
temp暂存即将被覆盖的dp[j]（它将成为下一轮的prev） - 状态转移仍为：
dp[j] = min({dp[j]+1, dp[j-1]+1, prev + (s1[i-1]!=s2[j-1])}) - 务必先交换
prev和temp，再更新dp[j]，否则逻辑错乱
示例片段（假设 s1.size() ，否则交换）：
int levenshtein(const string& s1, const string& s2) {
if (s1.size() > s2.size()) return levenshtein(s2, s1);
int m = s1.size(), n = s2.size();
vector<int> dp(n + 1);
for (int j = 0; j <= n; ++j) dp[j] = j;
for (int i = 1; i <= m; ++i) {
int prev = dp[0]; // dp[i-1][0]
dp[0] = i;
for (int j = 1; j <= n; ++j) {
int temp = dp[j];
dp[j] = min({dp[j] + 1, dp[j-1] + 1, prev + (s1[i-1] != s2[j-1])});
prev = temp;
}
}
return dp[n];
}
边界条件与字符比较的坑：空字符串、大小写、Unicode
Levenshtein 定义本身对空字符串天然友好（dp[i][0]=i, dp[0][j]=j），但实现时容易漏掉初始化或索引偏移。更常踩的坑在字符层面：
- 误用
s1[i]直接比较 —— 必须是s1[i-1]，因为dp[i][j]对应前i个字符，索引从 0 开始 - 大小写敏感是默认行为，若需忽略，应提前统一转小写，而非在比较时用
tolower—— 后者对非 ASCII 字符（如中文、emoji）未定义 - C++
string是字节序列，不支持 Unicode code point 级别比较；若输入含 UTF-8 多字节字符，直接按char比较会出错（比如把一个汉字拆成多个char判不等） - 生产环境建议加断言：
assert(!s1.empty() || !s2.empty())，避免全零长度导致未定义行为
性能敏感场景下的进一步优化点
当字符串极长或调用频次极高（如实时拼写检查后台），仅空间优化不够，还需关注常数级开销：
- 用原生数组替代
vector：若长度已知上限，int dp[10000]比vector少一次堆分配 - 提前终止：若当前行最小值已超过预设阈值（如只关心距离 ≤ 3 的相似词），可在内层循环中维护
min_in_row并break - 短路判断：若
abs((int)s1.size() - (int)s2.size()) > threshold，直接返回 > threshold，避免进 DP - 注意
min({a,b,c})在老版本 GCC 中需<initializer_list>，可改用嵌套min(a, min(b,c))兼容 C++11
真正难的不是写出 O(n) 空间解法，而是在保持逻辑清晰的前提下，让每个 ++j、每次 prev = temp 都有明确的物理含义——DP 数组的“时间切片”感一旦丢失，调试成本会指数上升。
