编辑距离（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) 的最小编辑距离。状态转移由末尾字符是否相等决定：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

• 若 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<int>> dp(m+1, vector<int>(n+1));
    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int j = 0; j <= n; ++j) dp[0][j] = j;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            dp[i][j] = word1[i-1] == word2[j-1] ?
                dp[i-1][j-1] : 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
    return dp[m][n];
}

边界情况与常见错误 容易忽略空字符串、相同字符串、超长字符串带来的问题：

• word1 或 word2 为空时，返回另一方长度——但若未正确初始化 dp 边界，会访问越界或得到 0
• 字符比较写成 word1[i] == word2[j]（越界），应始终用 i-1 和 j-1
• 使用 int 存储距离足够，但若字符串长达 10⁵，二维数组会爆内存——此时需改用一维 + 滚动，或考虑启发式剪枝（如限制最大距离阈值）
• 某些题目要求“仅允许替换和插入”，这时删除操作不合法，转移方程要去掉 dp[i-1][j] 项

如何回溯编辑操作序列 仅算距离不够时，需记录每步决策。在填表时同步维护 op[i][j]（例如 0=匹配、1=替换、2=删除、3=插入），然后从 dp[m][n] 往回走：

• 若 word1[i-1] == word2[j-1]，往 dp[i-1][j-1] 走，操作为“保留”
• 否则比较三个来源值，选最小的那个方向，并对应添加操作
• 注意：回溯路径是反的，最后要反转操作列表
• 若用一维 DP，无法直接回溯——必须保留完整二维表或额外存 parent 指针

真正难的不是写出基础 DP，而是根据题意调整操作集合、处理大输入、或在 O(1) 空间内判断是否距离 ≤ k（这时得用双指针或 BFS 剪枝）。这些变体不改核心逻辑，但容易在边界和状态定义上出错。