洛谷P2758题解：动态规划求解编辑距离的完整攻略

胡志明t

一、题目解读

洛谷P2758题要求计算两个字符串之间的编辑距离，即通过插入、删除、替换三种操作将字符串A转换为B所需的最小操作次数。题目考察的核心是动态规划算法在字符串匹配中的应用，需要找到**的状态转移路径。

二、解题思路

采用动态规划（Dynamic Programming）策略。核心思想是构建二维dp数组，dp[j]表示A的前i个字符转换为B的前j个字符的最小操作次数。通过初始化边界条件（空串转换的情况）和状态转移方程（字符相同时无需操作，不同时选择插入、删除、替换中的**解），最终得到dp[m][n]即为答案。

三、解题步骤

1. 输入与初始化：读取字符串A和B，记录长度m和n，创建dp数组。

2. 边界条件：dp[0] = i（删除A前i个字符），dp[0][j] = j（插入B前j个字符）。

3. 状态转移：

    若A[i-1] == B[j-1]，则dp[j] = dp[i-1][j-1]（无需操作）。

    否则，计算三种操作的最小值：插入（dp[j-1] + 1）、删除（dp[i-1][j] + 1）、替换（dp[i-1][j-1] + 1）。

4. 输出结果：dp[m][n]即为最小编辑距离。

四、代码与注释

1. #include <iostream>
   
2. #include <string>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     string A, B;
   
8.     cin >> A >> B;   // 输入两个字符串
   
9.     int m = A.length(), n = B.length();
   
10.    
    
11.     // dp[i][j]表示A的前i个字符转换为B的前j个字符的最小操作次数
    
12.     int dp[m+1][n+1];
    
13.    
    
14.     // 初始化边界条件
    
15.     for(int i = 0; i <= m; i++) dp[i][0] = i; // 删除i次
    
16.     for(int j = 0; j <= n; j++) dp[0][j] = j; // 插入j次
    
17.    
    
18.     for(int i = 1; i <= m; i++) {
    
19.         for(int j = 1; j <= n; j++) {
    
20.             if(A[i-1] == B[j-1]) {
    
21.                 // 字符相同，无需操作
    
22.                 dp[i][j] = dp[i-1][j-1];
    
23.             } else {
    
24.                 // 取三种操作中的最小值：插入、删除、替换
    
25.                 dp[i][j] = min({
    
26.                     dp[i][j-1] + 1,    // 插入
    
27.                     dp[i-1][j] + 1,    // 删除
    
28.                     dp[i-1][j-1] + 1   // 替换
    
29.                 });
    
30.             }
    
31.         }
    
32.     }
    
33.    
    
34.     cout << dp[m][n] << endl;   // 输出最小编辑距离
    
35.     return 0;
    
36. }

复制代码

五、总结

本文通过动态规划方法解决了洛谷P2758的编辑距离问题，关键点在于理解dp数组的构建逻辑与状态转移方程。通过清晰的边界条件和三种操作的优化选择，实现了高效求解。代码简洁且注释明确，适合算法学习者参考实践。

来源：洛谷题解