编辑距离（levenshtein distance）指将字符串a转换为字符串b所需的最少单字符操作次数（插入、删除、替换）；用动态规划求解因其具备最优子结构和重叠子问题，通过dpi表示前i、j字符的最小距离，按字符是否相等分情况递推，避免贪心错误并保证全局最优。
什么是编辑距离，为什么用动态规划解
编辑距离（Levenshtein Distance）指将字符串 A 变成字符串 B 所需的最少单字符操作次数（插入、删除、替换）。它不是贪心能解决的问题——比如 "ab" → "ba"，看似交换最直接，但编辑距离只允许单字符操作，必须先删再插或替换，结果是 2。动态规划能穷举所有子问题的最优解，天然适配这类“依赖前序状态”的转换问题。
核心思路：定义 dp[i][j] 表示 A.substr(0,i) 到 B.substr(0,j) 的最小编辑距离。状态转移由末尾字符是否相等决定：
- 若
A[i-1] == B[j-1]，则dp[i][j] = dp[i-1][j-1] - 否则，取三种操作的最小值：
min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
标准二维 DP 实现与空间优化
二维数组写法最直观，但空间复杂度为 O(m*n)。实际中常优化为一维——因为 dp[i][j] 只依赖上一行和左邻元素，可用两个一维数组或滚动数组。
关键细节：
- 初始化：
dp[0][j] = j（B 前 j 个字符全靠插入），dp[i][0] = i（A 前 i 个全靠删除） - 滚动数组时，需缓存左上角值（即原
dp[i-1][j-1]），否则会被覆盖 - 若只需距离值，不用回溯路径，一维优化安全；若要输出具体操作序列，必须保留二维或额外记录决策
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector>> dp(m+1, vector<int>(n+1));
for (int i = 0; i
<h3>边界情况与常见错误
容易忽略空字符串、相同字符串、超长字符串带来的问题：
<ul>
<li>
<code>word1</code> 或 <code>word2</code> 为空时，返回另一方长度——但若未正确初始化 <code>dp</code> 边界，会访问越界或得到 0</li>
<li>字符比较写成 <code>word1[i] == word2[j]</code>（越界），应始终用 <code>i-1</code> 和 <code>j-1</code>
</li>
<li>使用 <code>int</code> 存储距离足够，但若字符串长达 10⁵，二维数组会爆内存——此时需改用一维 + 滚动，或考虑启发式剪枝（如限制最大距离阈值）</li>
<li>某些题目要求“仅允许替换和插入”，这时删除操作不合法，转移方程要去掉 <code>dp[i-1][j]</code> 项</li>
</ul>
<h3>如何回溯编辑操作序列
仅算距离不够时，需记录每步决策。在填表时同步维护 <code>op[i][j]</code>（例如 0=匹配、1=替换、2=删除、3=插入），然后从 <code>dp[m][n]</code> 往回走：
<ul>
<li>若 <code>word1[i-1] == word2[j-1]</code>，往 <code>dp[i-1][j-1]</code> 走，操作为“保留”</li>
<li>否则比较三个来源值，选最小的那个方向，并对应添加操作</li>
<li>注意：回溯路径是反的，最后要反转操作列表</li>
<li>若用一维 DP，无法直接回溯——必须保留完整二维表或额外存 parent 指针</li>
</ul>
真正难的不是写出基础 DP，而是根据题意调整操作集合、处理大输入、或在 O(1) 空间内判断是否距离 ≤ k（这时得用双指针或 BFS 剪枝）。这些变体不改核心逻辑，但容易在边界和状态定义上出错。</h3>
</h3></int></vector>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
