莱文斯坦距离是两字符串通过插入、删除、替换操作相互转换的最少步骤数；其满足最优子结构与重叠子问题，故用动态规划求解，时间复杂度o(mn)，二维dp状态dpi表示s1前i字符变s2前j字符的最小编辑距离。

什么是莱文斯坦距离，为什么用动态规划

莱文斯坦距离就是两个字符串之间，通过插入、删除、替换操作把一个变成另一个所需的最少步骤数。它天然适合用动态规划——因为每个位置的最小编辑距离只依赖于左、上、左上三个相邻状态，存在明确的子问题重叠和最优子结构。

直接递归会指数级爆炸，而二维 DP 表能把时间复杂度压到 O(m*n)，空间也可优化到 O(min(m,n))，但初学建议先写清楚二维版本。

二维 DP 数组怎么初始化和转移

设 dp[i][j] 表示 s1 前 i 个字符变成 s2 前 j 个字符的最小编辑距离。

• 边界：空字符串变长度为 j 的串，只能插入 j 次 → dp[0][j] = j；同理 dp[i][0] = i
• 转移：若 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1]；否则取三者最小值：dp[i-1][j] + 1（删），dp[i][j-1] + 1（插），dp[i-1][j-1] + 1（替）

注意下标偏移：字符串从 0 开始，DP 状态从 1 开始对齐，避免越界判断。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

C++ 实现时容易踩的坑

常见错误不是逻辑错，而是细节失控：

• dp 数组维度写反：应为 dp[m+1][n+1]，不是 [m][n] —— 否则无法容纳空串状态
• 忘记初始化第一行/列：直接用未定义值参与 min 计算，结果全错
• 比较字符时下标错位：比如写成 s1[i] == s2[j]，实际应是 s1[i-1] == s2[j-1]
• 没考虑空字符串输入：s1 或 s2 为空时，直接返回另一方长度更安全，但二维 DP 本身已覆盖该情况

示例片段（核心转移部分）：

for (int i = 1; i 

<h3>要不要优化空间？什么情况下必须保留二维</h3>
<p>如果只需要最终距离值，用滚动数组把空间降到 <code>O(n)</code> 完全可行；但如果要回溯出具体编辑操作序列（比如哪几步删/插/替），就必须保留完整二维表——因为路径重建依赖所有中间状态。</p>
<p>另外，调试阶段强烈建议先用二维实现并打印小规模 <code>dp</code> 表（比如 "ab" 和 "ac"），肉眼验证每格是否符合预期。很多“结果不对”的问题，其实一眼就能看出第 2 行第 2 列填错了。</p>

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！