编辑距离递推关系不越界的核心是：dpi表示s10..i)与s2[0..j)的最小编辑距离，初始化dp[i=i、dp0=j，递推时i、j从1开始，状态转移为dpi=min(dpi-1+1, dpi+1, dpi-1+(s1[i-1]!=s2[j-1]))。
编辑距离的递推关系怎么写才不越界
核心是定义 dp[i][j] 表示 s1.substr(0, i) 到 s2.substr(0, j) 的最小编辑距离。很多人直接从 1 开始循环，但忘了初始化第 0 行和第 0 列——它们对应空字符串到非空字符串的代价，必须显式设为 i 或 j。
常见错误是把循环写成 for (int i = 0; i 却没处理 <code>i == 0 或 j == 0 的边界，导致访问 dp[-1][j] 或下标错位。正确做法是申请 (n+1) × (m+1) 的二维数组，让 i 和 j 代表长度而非下标。
-
dp[0][j] = j：插入j个字符把空串变成s2[0..j-1] -
dp[i][0] = i：删除i个字符把s1[0..i-1]变成空串 - 主循环从
i = 1、j = 1开始，状态转移用：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])})
用 vector> 还是滚动数组
如果只关心最终距离值（比如拼写检查中阈值判断），不需要回溯操作路径，那么二维 vector 是最直觉的选择；但空间复杂度是 O(m×n)，长字符串（如 >10k 字符）容易爆内存或触发频繁分配。
实际项目中更推荐滚动数组优化：只保留两行 dp[2][max_len+1]，用 i & 1 切换当前行。注意每次迭代前要重置当前行，否则残留值会污染结果。
立即学习“C++免费学习笔记（深入）”；
- 滚动数组写法里，
dp[0]存上一行，dp[1]存当前行 - 更新时先拷贝
dp[0][0]到dp[1][0]（即空串到空串为 0），再逐列计算 - 别漏掉
dp[1][0] = i—— 这是「当前长度为 i 的 s1 变为空串」的代价，不是常量
Levenshtein 距离和实际拼写检查的差距在哪
标准编辑距离只算插入、删除、替换三种操作，每种代价为 1。但真实拼写检查中，“teh → the” 这类相邻字符交换（transposition）很常见，而它需要两次操作（删+插），得分是 2，不如一个拼错字母得分低，导致排序靠后。
解决办法不是重写整个 DP，而是加一层后处理：对所有候选词，额外计算一次 Damerau-Levenshtein 距离（支持交换），但仅当原距离 ≤2 时才启用——避免全量扫描开销。也可以预生成常见交换对（如 "ab" ↔ "ba"）做哈希快速匹配。
- 交换操作只能发生在
i > 0 && j > 0 && s1[i-1] == s2[j-2] && s1[i-2] == s2[j-1]时才合法 - 此时可尝试
min(dp[i][j], dp[i-2][j-2] + 1)，前提是i >= 2 && j >= 2 - 很多库（如
boost::algorithm::levenshtein_distance）默认不包含交换，得自己补
为什么 std::string_view 能加速但不能直接用于 dp 数组
传参用 std::string_view 避免拷贝是合理的，尤其在高频调用拼写检查函数时；但 dp 数组本身存的是整数，跟字符串视图无关。有人误以为用 string_view 就能省掉 substr 开销，其实不然——DP 过程中仍需随机访问单个字符，而 string_view 的 operator[] 和 std::string 一样是 O(1)，没有额外收益。
真正影响性能的是缓存局部性：连续访问 s1[i-1] 和 s2[j-1] 时，若两个字符串内存不邻近，CPU 缓存行可能反复切换。实践中，把短候选词批量加载进紧凑 buffer 再统一计算，比单次调用快 20%+。
- 不要对
string_view做.data()指针比较来判断相等——生命周期管理容易出错 - DP 循环内避免任何函数调用（包括
.size()），提前提取n = s1.size()、m = s2.size() - 编译器对
const char*输入的优化往往比string_view更激进，小字符串场景可考虑重载
