Levenshtein距离DP状态应定义为dpi表示s1前i个字符变为s2前j个字符的最小编辑步数，需开m+1数组并初始化第0行第0列，i、j从1开始递推，注意s1[i-1]与s2[j-1]的索引偏移。
Levenshtein距离的DP状态怎么定义才不越界
二维DP数组 dp[i][j] 表示 s1 前 i 个字符变成 s2 前 j 个字符所需的最小编辑步数。关键点是：下标从 0 开始，但 dp[0][j] 和 dp[i][0] 必须初始化——它们对应空字符串到非空字符串的插入/删除操作数。
常见错误是把 dp 开成 [m][n] 却用 i=1..m、j=1..n 递推，却忘了初始化第 0 行第 0 列；更稳妥的做法是开 [m+1][n+1]，让 dp[0][j] = j、dp[i][0] = i，然后从 i=1、j=1 开始填表。
状态转移时如何处理字符相等和不等
当 s1[i-1] == s2[j-1] 时，不需要操作，直接继承左上角：dp[i][j] = dp[i-1][j-1]；否则取三种操作的最小值：min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，分别对应删除、插入、替换。
-
dp[i-1][j]：删掉s1[i-1]，再把前i-1个字符变到s2前j个 -
dp[i][j-1]：在s1末尾插入s2[j-1]，再把前i个变到前j-1个 -
dp[i-1][j-1]：替换s1[i-1]为s2[j-1]，再处理前面
空间优化：一维数组能跑吗
可以，因为每次只依赖上一行和左邻元素，用两个一维数组（prev 和 curr）或滚动的一维数组加临时变量即可。但要注意：必须从左到右更新，且需缓存左上角旧值（即未被覆盖的 prev[j-1]）。
立即学习“C++免费学习笔记（深入）”；
典型写法是：
for (int j = 1; j <= n; ++j) {
int tmp = curr[j]; // 保存即将被覆盖的 curr[j]，它下轮会成为左上角
curr[j] = (s1[i-1] == s2[j-1]) ? prev[j-1] : min({prev[j], curr[j-1], prev[j-1]}) + 1;
prev[j-1] = tmp;
}
若直接用单数组 dp[j]，必须用变量 diag 显式存 dp[j-1] 的旧值，否则 dp[j-1] 已被更新，丢失左上信息。
边界和性能要注意什么
输入为空串时，结果就是另一串长度，可提前返回；长度差过大（比如 > 1000）时，朴素 O(mn) DP 可能超时或爆栈——这时应考虑带阈值的优化版本（如只计算对角线附近带状区域），或改用 std::string_view 避免拷贝。
- 不要用
std::string::substr在循环里反复切片，会触发多次内存分配 - C++17 起可用
std::string_view接收参数，避免构造临时std::string - 若只需判断距离是否 ≤ k（如拼写纠错），可用 O(k·min(m,n)) 的算法，不必算完整矩阵
最易被忽略的是：字符串索引和DP下标错位——s1[i-1] 对应 dp[i][j]，这个 -1 偏移在手写循环时极易漏掉，导致访问越界或逻辑错误。
