编辑距离是将一个字符串转换为另一个所需的最少单字符操作数（插入、删除、替换），因其暴力递归呈指数复杂度，故采用动态规划：用dpi表示s1前i字符变s2前j字符的最小代价，通过二维数组或滚动数组（空间O(min(m,n))）实现，注意边界初始化和s1[i-1]与s2[j-1]的索引对齐。
编辑距离是什么，为什么用动态规划
编辑距离（Levenshtein Distance）指把一个字符串变成另一个所需的最少单字符操作数（插入、删除、替换）。它不是简单比长度或逐字符判等，而是要穷举所有可能路径——暴力递归会指数爆炸，dp[i][j] 表示 s1 前 i 个字符变到 s2 前 j 个字符的最小代价，状态转移自然且可复用。
标准 DP 实现：二维数组 vs 滚动数组
二维写法最直观，但空间是 O(m*n)；实际只需前一行和当前行，用两个一维数组就能压到 O(min(m,n))。注意索引偏移：通常让 dp[0][j] = j（空串变 s2.substr(0,j) 需插 j 次），dp[i][0] = i 同理。
常见错误：循环从 i=0 或 j=0 开始却没初始化边界，导致访问未定义内存；或者把字符比较写成 s1[i] == s2[j]（下标越界，应为 s1[i-1] == s2[j-1]）。
示例核心逻辑：
立即学习“C++免费学习笔记（深入）”；
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
}
}
如何避免重复计算和越界访问
输入为空串时直接返回另一串长度，别让 DP 循环跑；用 size_t 容易在 j-1 时回绕成极大值，一律用 int 索引；如果只关心是否 ≤ 某阈值（比如拼写纠错限 2 步），可在 DP 过程中加剪枝：if (dp[i][j] > threshold) dp[i][j] = threshold + 1;，后续只取 min，能提前终止部分计算。
-
s1和s2建议传 const 引用，避免拷贝 - 若频繁调用，可预分配
dp数组并复用内存 - UTF-8 字符串不能直接按 byte 处理，需先转 UTF-32 或用库如
utf8cpp提取 code point
std::string 与 C 风格字符串的处理差异
std::string 直接用 .size() 和 [] 下标安全（只要不越界）；C 风格字符串（const char*）必须先用 strlen 获取长度，且要注意末尾 '\0' 不参与编辑距离计算——也就是说，比较的是有效内容长度，不是整个缓冲区。
容易被忽略的一点：Windows 下若文件读入含 \r\n 而 Linux 是 \n，同一文本在不同平台算出的编辑距离会不同。预处理统一换行符能避免这种隐性偏差。
