一、题目解读
洛谷P2758题要求计算两个字符串之间的编辑距离,即通过插入、删除、替换三种操作将字符串A转换为B所需的最小操作次数。题目考察的核心是动态规划算法在字符串匹配中的应用,需要找到最优的状态转移路径。
二、解题思路
采用动态规划(Dynamic Programming)策略。核心思想是构建二维dp数组,dp[i][j]表示A的前i个字符转换为B的前j个字符的最小操作次数。通过初始化边界条件(空串转换的情况)和状态转移方程(字符相同时无需操作,不同时选择插入、删除、替换中的最优解),最终得到dp[m][n]即为答案。
三、解题步骤
输入与初始化:读取字符串A和B,记录长度m和n,创建dp数组。
边界条件:dp[i][0] = i(删除A前i个字符),dp[0][j] = j(插入B前j个字符)。
状态转移:
若A[i-1] == B[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[m][n]即为最小编辑距离。
四、代码与注释
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string A, B;
cin >> A >> B; // 输入两个字符串
int m = A.length(), n = B.length();
// dp[i][j]表示A的前i个字符转换为B的前j个字符的最小操作次数
int dp[m+1][n+1];
// 初始化边界条件
for(int i = 0; i <= m; i++) dp[i][0] = i; // 删除i次
for(int j = 0; j <= n; j++) dp[0][j] = j; // 插入j次
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(A[i-1] == B[j-1]) {
// 字符相同,无需操作
dp[i][j] = dp[i-1][j-1];
} else {
// 取三种操作中的最小值:插入、删除、替换
dp[i][j] = min({
dp[i][j-1] + 1, // 插入
dp[i-1][j] + 1, // 删除
dp[i-1][j-1] + 1 // 替换
});
}
}
}
cout << dp[m][n] << endl; // 输出最小编辑距离
return 0;
}
五、总结
本文通过动态规划方法解决了洛谷P2758的编辑距离问题,关键点在于理解dp数组的构建逻辑与状态转移方程。通过清晰的边界条件和三种操作的优化选择,实现了高效求解。代码简洁且注释明确,适合算法学习者参考实践。
来源:洛谷题解