CSP-J 入门级 · CSP 2023 入门级第一轮 第 20 题

2. （编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl;
 

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考编辑距离的DP递推。拿到题先想：空串对空串是0，空串对长度j要j次插入，长度i对空串要i次删除。然后看当前两个字符，相等就继承对角线，不等就取插入、删除、替换三种的最小值加1。

最容易把初始化搞反：dp[0][j]是j（插入），dp[i][0]是i（删除），很多人记成dp[0][j]=i。还有判断字符相等时，循环下标是i和j，但字符串下标得减1，写成str1[i]==str2[j]会越界或逻辑错。另外转移方程里替换操作对应的是dp[i-1][j-1]，别误填成dp[i][j]或dp[i-1][j]，那样算出来的距离会偏大。

编辑距离 DP 填空详解

考点与概念

这道题考的是经典的编辑距离（Edit Distance），也叫 Levenshtein 距离。核心思想是用动态规划：dp[i][j] 表示把 str1 的前 i 个字符变成 str2 的前 j 个字符最少要几步。允许三步操作：插入、删除、替换，每步代价都是 1，求全局最小值。