编辑距离（Levenshtein）问题怎么解？

直接回答：二维 DP。dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。若 word1[i−1] == word2[j−1]，dp[i][j] = dp[i−1][j−1]；否则取三种操作的最小值加一：插入 dp[i][j−1]+1、删除 dp[i−1][j]+1、替换 dp[i−1][j−1]+1。初始化 dp[i][0]=i、dp[0][j]=j。时间 O(mn)、空间可压缩到 O(n)。

展开解析：这题的价值在于建立「字符串对齐」类 DP 的通用思维：两个序列的比对问题用二维表，状态含义是「前缀对前缀」的最优解，转移对应最后的对齐决策。同族题：最长公共子序列（只有增删没有替换时编辑距离退化为 m+n−2·LCS）、不同的子序列、两个字符串的删除操作。工程应用是加分项：拼写纠错、DNA 序列比对、git diff 的相似度计算、输入法候选排序。优化与追问：只保留两行甚至一行滚动数组；需要回溯具体操作路径时记录决策来源；加权编辑距离（不同操作不同代价）只需改转移中的 +1；上界裁剪（如 Ukkonen 算法按带宽填表）把实际开销降到 O(k·n)。

示例：

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        cur = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[n]