Levenshtein距离的DP状态定义为dpi，是因为它精确表示s1前i个字符转换为s2前j个字符的最少编辑操作数，自然覆盖删、增、换三种操作，且边界dp0=j、dpi=i符合空串转换逻辑，确保转移无错位。
Levenshtein距离的DP状态定义为什么是dp[i][j]？
因为要比较两个字符串 s1（长 m）和 s2（长 n）的编辑距离，dp[i][j] 必须表示「s1 前 i 个字符」变成「s2 前 j 个字符」所需的最少操作数。这个定义天然覆盖了三种操作：删（dp[i-1][j] + 1）、增（dp[i][j-1] + 1）、换（dp[i-1][j-1] + (s1[i-1] != s2[j-1])）。如果反过来定义成「后缀」或用 1-based 索引但不统一偏移，边界初始化和转移就会错位。
常见错误现象：dp[0][j] 被设为 j-1 或漏初始化；i、j 循环从 1 开始但访问 s1[i] 导致越界；用 string::at() 未检查抛异常。
-
dp[0][j]=j（把空串变s2前 j 字符，只能插入 j 次） -
dp[i][0]=i（同理，只能删除 i 次） - 循环变量
i和j从 1 到m、n，对应访问s1[i-1]和s2[j-1]
如何把二维DP压缩成一维数组？
观察转移只依赖上一行（dp[i-1][*]）、当前行左侧（dp[i][j-1]）和左上（dp[i-1][j-1]），可用两个一维数组交替，甚至仅用一个数组 + 临时变量保存左上角值。空间从 O(m*n) 降到 O(min(m,n))。
关键点在于：更新 dp[j] 前，必须先缓存旧的 dp[j-1]（即上一轮的左上值），否则会被覆盖。很多人直接写 dp[j] = min({dp[j]+1, dp[j-1]+1, prev + (s1[i-1]!=s2[j-1])}) 却忘了 prev 要在每次内层循环开始前更新为旧的 dp[j]。
- 先设
vector，初始化为dp(n+1) 0,1,...,n - 外层遍历
i从 1 到 m，内层j从 1 到 n - 用
int prev = dp[0]; dp[0] = i;初始化每行首项，然后for j=1..n中：先int tmp = dp[j];，再更新dp[j]，最后prev = tmp;
为什么std::string传参要用const std::string&？
Levenshtein 计算常用于高频比对（如模糊搜索、拼写纠错），若按值传递 std::string，每次调用会触发深拷贝，尤其长字符串时开销显著。而 const std::string& 避免复制，且保证函数内不修改原串——这对算法纯度和线程安全都有意义。
容易被忽略的细节：std::string_view 更轻量，但需确保传入的字符串生命周期长于函数调用；若输入可能来自临时对象（如 func("abc" + "def")），用 std::string_view 可能悬垂，此时仍应选 const std::string&。
- 接口签名应为：
int levenshtein(const std::string& s1, const std::string& s2) - 若确定输入稳定且追求极致性能（如预处理词典），可重载接受
std::string_view - 不要用
char*，丢失长度信息且易出strlen开销或越界
实际使用时要注意哪些边界和性能陷阱？
Levenshtein 在短字符串（≤50 字符）上很快，但时间复杂度是 O(m*n)，一旦字符串超几百字符，耗时会陡增。生产环境不能无条件调用，必须加保护。
典型问题：用户输入含控制字符或 emoji（UTF-8 多字节），直接按 std::string 字节操作会导致“一个 emoji 算多个字符”，距离失真；或空串、单字符串没走快速路径，白白建 DP 表。
- 开头加短路判断：
if (s1 == s2) return 0;，if (s1.empty()) return s2.size();等 - 长度差 > 某阈值（如 100）直接返回大数，避免无效计算
- 需要 Unicode 正确性时，先用 ICU 或
utf8cpp将字符串转为std::vector再计算 - 频繁调用场景建议预分配
dp向量并复用，而非每次new或resize
最易被忽略的是：Levenshtein 距离本身不归一化，直接比较不同长度字符串的距离没有意义；业务中通常要除以 max(len1, len2) 得相似度，这步必须由调用方完成，算法内部不做。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
