CSP-J 2023 第一轮 第 42 题：编辑距离：⑤处应填

题目

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;
    return 0;
}

⑤处应填（ ）

选项

• A. dp[i][j] + 1
• B. dp[i-1][j-1]+1
• C. dp[i-1][j-1]
• D. dp[i][j]

答案

C

题解

选 C. dp[i-1][j-1]。

定义 dp[i][j] 为：将 str1 的前 i 个字符变成 str2 的前 j 个字符，所需的最少操作次数。

当最后一个字符不相同时，有三种处理方式：

• 插入：先把前 i 个字符变成目标的前 j-1 个字符，再插入目标的第 j 个字符，代价是 dp[i][j-1] + 1。
• 删除：删除原串的第 i 个字符，剩下的前 i-1 个字符变成目标的前 j 个字符，代价是 dp[i-1][j] + 1。
• 替换：先将双方前面的字符匹配好，再把原串的第 i 个字符替换成目标的第 j 个字符，代价是 dp[i-1][j-1] + 1。

因此： ``cpp dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]); ``

外面已经加了 1，所以⑤处不需要再加 1。