标准二维DP不推荐因空间O(m×n)、缓存不友好，如10k字符串需约400MB内存；应改用一维滚动数组优化至O(min(m,n))，并严格初始化边界（dpi=i, dp0=j）、处理UTF-8需转u32string。
Levenshtein 距离用标准二维 DP 实现内存开销大、缓存不友好，实际项目中应优先用一维滚动数组优化，且必须注意边界初始化和索引偏移。
为什么标准二维 dp[i][j] 在 C++ 中不推荐直接用
标准实现需 dp 数组大小为 (m+1) * (n+1)，对长字符串（如 10k 字符）会分配上亿个 int，不仅耗内存，还因随机访问破坏 CPU 缓存局部性。更关键的是，每次只依赖上一行和左邻值，二维存储纯属冗余。
- 必须用
std::vector<int></int>而非裸new int[]，避免异常安全问题 - 初始化时第 0 行（空字符串到
s2[0..j-1]）必须设为j，第 0 列同理——漏掉这个会导致所有结果偏小 - 若字符串含 Unicode（UTF-8），不能直接按
char算长度，得先转std::u32string或用 ICU 库预处理
一维滚动数组的正确写法：prev 和 curr 怎么交替
核心是只保留两行：上一行 prev[j] 对应 dp[i-1][j]，当前行 curr[j] 构建 dp[i][j]。注意 curr[0] 始终是 i（删完 s1[0..i-1]），而 prev[0] 是 i-1。
int levenshtein(const std::string& s1, const std::string& s2) {
int m = s1.size(), n = s2.size();
std::vector<int> prev(n + 1), curr(n + 1);
for (int j = 0; j <= n; ++j) prev[j] = j;
for (int i = 1; i <= m; ++i) {
curr[0] = i; // 删除 s1[0..i-1] 的代价
for (int j = 1; j <= n; ++j) {
int del = prev[j] + 1;
int ins = curr[j-1] + 1;
int sub = prev[j-1] + (s1[i-1] == s2[j-1] ? 0 : 1);
curr[j] = std::min({del, ins, sub});
}
prev.swap(curr); // 交换引用，避免拷贝
}
return prev[n];
}
std::min({a,b,c}) 在旧编译器报错怎么办
GCC 4.7+ / Clang 3.1+ 支持 initializer_list 版 std::min，但 VS2015 及更早版本只认两个参数重载。强行用三元嵌套又难读，稳妥做法是：
立即学习“C++免费学习笔记（深入）”；
- 用
std::min(std::min(del, ins), sub)—— 兼容所有 C++11 编译器 - 若已用 C++14 以上，可加
using std::min;后直接调min({del,ins,sub}) - 禁止用宏定义
#define MIN3(a,b,c) ...，会破坏类型安全和调试信息
性能敏感场景还要注意这三点
当批量计算相似度（如拼写纠错候选排序），光靠一维优化不够：
- 提前终止：若当前行最小值已超阈值（如 >5），可直接返回 -1 表示“不相似”，省去后续计算
- 短字符串特化：当
std::min(m,n) ，直接用查表法或展开循环，比分支预测更稳 - 字符比较加速：对 ASCII 字符串，用
memcmp替代逐字符==无意义——因为 Levenshtein 必须逐位置决策，无法跳过
真正卡点的从来不是算法复杂度，而是 cache line 命中率和分支预测失败率；把 prev 和 curr 声明为 std::vector 并 reserve 好容量，比纠结内联函数有用得多。
