动态规划入门：洛谷P2758编辑距离问题详解

一、解题思路

编辑距离是衡量两个字符串相似程度的重要指标，定义为将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。洛谷P2758题目要求我们实现这一算法，核心在于理解动态规划的状态转移过程。

二、完整代码

#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;
}

三、代码解析

1. 数据结构定义

• dp[m+1][n+1]：二维数组存储子问题解，dp[i][j]表示A前i字符转B前j字符的最小操作数

2. 边界条件初始化

• dp[i][0] = i：将A前i字符转为空串需i次删除

• dp[0][j] = j：将空串转为B前j字符需j次插入

3. 状态转移方程

• 插入：dp[i][j-1] + 1

• 删除：dp[i-1][j] + 1

• 替换：dp[i-1][j-1] + 1

• 字符相同时：直接继承左上角值(dp[i-1][j-1])

• 字符不同时：取三种操作最小值+1

四、动态规划四步法解析

1. 定义状态：明确dp[i][j]表示A前i字符→B前j字符的最小操作数

2. 初始状态：处理空串转换的边界情况

3. 状态转移：根据字符是否相同选择不同策略

4. 最终解：dp[m][n]即为完整字符串转换的最小操作数