动态规划解决编辑距离（Edit Distance）问题 问题描述 编辑距离（Levenshtein距离）是衡量两个字符串相似度的指标，定义为将字符串A转换为字符串B所需的最少单字符编辑操作次数。允许的操作包括：插入一个字符、删除一个字符、替换一个字符。例如，"kitten"和"sitting"的编辑距离为3（k→s替换、e→i替换、末尾插入g）。 动态规划思路分析 问题分解 ：将长字符串的转换分解为子问题。若A[ 0..i]和B[ 0..j]分别表示A的前i个字符和B的前j个字符，则编辑距离dp[ i][ j ]可通过更短的子串推导。 状态定义 ：设dp[ i][ j ]表示将A的前i个字符转换为B的前j个字符所需的最小操作次数。 边界情况 ： 若A为空（i=0），需插入j个字符，dp[ 0][ j ] = j。 若B为空（j=0），需删除i个字符，dp[ i][ 0 ] = i。 状态转移方程 ： 若A[ i-1] == B[ j-1]（末尾字符相同）：无需操作，dp[ i][ j] = dp[ i-1][ j-1 ]。 否则，取三种操作的最小值加1： 替换 ：将A[ i-1]替换为B[ j-1]，代价为dp[ i-1][ j-1 ] + 1。 删除 ：删除A[ i-1]，代价为dp[ i-1][ j ] + 1。 插入 ：在A末尾插入B[ j-1]，等价于B删除一个字符，代价为dp[ i][ j-1 ] + 1。 公式： \[ dp[ i][ j ] = \begin{cases} dp[ i-1][ j-1] & \text{if } A[ i-1] = B[ j-1 ] \\ \min(dp[ i-1][ j-1], dp[ i-1][ j], dp[ i][ j-1 ]) + 1 & \text{otherwise} \end{cases} \] 示例推导（A="kitten", B="sitting"） 初始化dp表（行列长度分别为len(A)+1和len(B)+1）： 第一行dp[ 0][ j ] = j（0,1,2,...,7） 第一列dp[ i][ 0 ] = i（0,1,2,...,6） 逐行计算（i=1..6, j=1..7）： i=1,j=1：A[ 0]='k', B[ 0 ]='s'，不同。比较： 替换：dp[ 0][ 0 ]+1=0+1=1 删除：dp[ 0][ 1 ]+1=1+1=2 插入：dp[ 1][ 0 ]+1=1+1=2 取最小值1，dp[ 1][ 1 ]=1。 后续关键步骤： i=6,j=7时，A[ 5]='n', B[ 6 ]='g'，不同。比较： 替换：dp[ 5][ 6 ]+1=2+1=3（"kitte"→"sittin"代价2，替换'n'为'g'） 删除：dp[ 5][ 7 ]+1=3+1=4 插入：dp[ 6][ 6 ]+1=3+1=4 最终dp[ 6][ 7 ]=3。 结果：dp[ 6][ 7 ]=3即为编辑距离。 优化与扩展 空间优化 ：实际只需两行数组滚动存储，空间复杂度从O(mn)降至O(min(m,n))。 操作记录 ：可通过辅助数组记录操作类型，反向回溯输出具体编辑步骤。 应用场景 ：拼写检查、DNA序列比对、自然语言处理中的相似度计算。 此方法通过动态规划将指数级暴力搜索优化为O(mn)时间复杂度的高效算法，体现了动态规划以空间换时间的核心思想。