编辑距离题解

休竹

2026-01-04 14:23:23

发布于：浙江

10阅读

0回复

0点赞

编辑距离

题解

如图所示， $A$ 串变成 $B$ 串最少字符操作次数和 $A$ 串前 $i$ 个字符变成 $B$ 串前 $j$ 个字符解决方法一样，即大问题和小问题解决方法一样
通过以下三种字符操作
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。

问题足够小可以直接解决
比如 $A$ 串为空串， $B$ 串长度为 $j$ $A-->B$ 插入操作做 $j$ 次即可
比如 $A$ 串长度为 $i$ ， $B$ 串长度为空串 $A-->B$ 删除操作做 $i$ 次即可

看大问题是否可以变成小问题，即假设子问题最优解已经得到，能否通过子问题最优解构建原问题的最优解

分析可得，具有最优子结构
设置 $dp[i][j]$ 表示将 $A$ 的前 $i$ 个字符转换为 $B$ 的前 $j$ 个字符的最小操作次数

初始化边界：

$dp[i][0] = i$ ： $A$ 的前 $i$ 个字符转为空串需 $i$ 次删除

$dp[0][j] = j$ ：空串转为 $B$ 的前 $j$ 个字符需 $j$ 次插入

状态转移方程：
若 $A[i] == B[j]：dp[i][j] = dp[i-1][j-1]$ （字符相同，无需操作）。
若 $A[i] != B[j]：dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)$
分别对应删除 $A[i]$ 、插入 $B[j]$ 、替换 $A[i]$ 为 $B[j]$ 三种操作

代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 2010; 
int dp[N][N], ans; 
// dp[i][j]表示将A的前i个字符转换为B的前j个字符的最小操作次数
string A, B;  
int main() {
    cin >> A >> B;
    int dA = A.size();   // 字符串A的长度
    int dB = B.size();   // 字符串B的长度
    // 在字符串前添加空格，使字符从下标1开始
    A = " " + A;
    B = " " + B;
    // 初始化dp数组边界条件
    for (int i = 1; i <= dA; i++)  dp[i][0] = i;  // A前i个字符转为空串：需i次删除
    for (int j = 1; j <= dB; j++)  dp[0][j] = j;  // 空串转为B前j个个字符：需j次插入

    for (int i = 1; i <= dA; i++) {
        for (int j = 1; j <= dB; j++) {
            if(A[i]==B[j]){
				dp[i][j]=dp[i-1][j-1];
			}else{
				dp[i][j]=min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;
			}
        }
    }
    // 输出结果：dp[dA][dB]即整个字符串的编辑距离
    cout << dp[dA][dB];
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

题解

热门讨论