编辑距离是将一个字符串转换为另一个所需的最少单字符操作数（插入、删除、替换），因其暴力递归呈指数复杂度，故采用动态规划：用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]）。
示例核心逻辑：
for (int i = 1; i <h3>如何避免重复计算和越界访问</h3> <p>输入为空串时直接返回另一串长度，别让 DP 循环跑；用 <code>size_t</code> 容易在 <code>j-1</code> 时回绕成极大值，一律用 <code>int</code> 索引；如果只关心是否 ≤ 某阈值（比如拼写纠错限 2 步），可在 DP 过程中加剪枝：<code>if (dp[i][j] > threshold) dp[i][j] = threshold + 1;</code>，后续只取 min，能提前终止部分计算。</p>
-
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，同一文本在不同平台算出的编辑距离会不同。预处理统一换行符能避免这种隐性偏差。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
