莱文斯坦距离的递推公式为：di = min(di-1+1, di+1, di-1+cost)，其中cost=0当s1[i-1]==s2[j-1]，否则为1；需用(m+1)×(n+1)数组并初始化首行首列为i、j以避免下标越界。
Levenshtein距离的递推公式怎么写对
直接套用教科书公式 dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(s1[i-1]!=s2[j-1])) 没问题，但下标越界是高频错误。必须让 dp 数组尺寸为 (m+1) x (n+1)，其中 m = s1.length()、n = s2.length()，且初始化 dp[i][0] = i、dp[0][j] = j。否则访问 dp[-1][*] 或 dp[*][-1] 会崩溃或结果错乱。
C++里用vector还是数组实现dp表更稳妥
用 std::vector<:vector>></:vector> 更安全，尤其当字符串长度不确定时。手动 new int*[m+1] 容易漏掉释放或越界。但要注意：二维 vector 构造有性能开销，若频繁调用且长度固定，可预分配：
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
别写成 vector<vector>>(m+1, vector<int>(n+1, 0))</int></vector> —— 默认初始化已为 0，显式赋 0 是冗余。
如何避免字符比较时的大小写干扰
Levenshtein 原算法区分大小写。如果需求是“忽略大小写”，不能在最后统一转小写再算（可能影响中间状态），而应在递推中处理：
立即学习“C++免费学习笔记（深入）”；
- 比较前统一转换：用
std::tolower(s1[i-1]) != std::tolower(s2[j-1]) - 注意
char可能为负，传给std::tolower前强转unsigned char，否则 UB - Windows 下
<cctype></cctype>的tolower对非 ASCII 字符无效，纯 ASCII 场景才放心用
空间优化到O(min(m,n))是否值得做
可以，但只省空间不提速。因为每次只依赖上一行，可用两个一维数组滚动更新：prev 和 curr。但代码变复杂，调试困难，且现代机器内存不紧张。除非你处理的是万级长度字符串且内存受限，否则不建议。更现实的优化点是：提前终止——当某轮计算中所有 curr[j] > threshold（比如阈值设为 5），直接返回 > threshold，避免完整计算。
边界 case 很容易被忽略：空字符串、一方为空、含 null 字符（\0）的 std::string 都合法，但若混用 C 风格字符串接口就危险。Levenshtein 本质只看字符序列，和编码无关，但你要确保传入的是真正想比的字节流。
