题意分析

题目要求计算将字符串 x 转换成字符串 y 所需的最小操作次数，允许的操作包括：

1. 删除：删除 x 中的一个字符。
2. 插入：在 x 中插入一个字符。
3. 替换：将 x 中的一个字符替换成另一个字符。

目标是找到最少的操作次数，使得 x 变成 y。

解题思路

这是一个经典的**编辑距离（Edit Distance）问题，可以使用动态规划（DP）**来求解。
设 dp[i][j] 表示 x 的前 i 个字符转换成 y 的前 j 个字符所需的最小操作次数。
状态转移方程如下：

• 如果 x[i-1] == y[j-1]，则 dp[i][j] = dp[i-1][j-1]（无需操作）。
• 否则，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1，分别对应替换、删除、插入操作。

初始化：

• dp[i][0] = i（删除 x 的所有字符）。
• dp[0][j] = j（插入 y 的所有字符）。

标程代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int MAX = 1005;

int main() {
    int m, n;
    string x, y;
    while (cin >> m >> x >> n >> y) {
        int dp[MAX][MAX] = {0};

        // 初始化边界条件
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        // 动态规划计算编辑距离
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x[i-1] == y[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1;
                }
            }
        }
        cout << dp[m][n] << endl;
    }
    return 0;
}

代码解释

1. 输入处理：读取 x 和 y 的长度及字符串。
2. 初始化 DP 表：
   • dp[i][0] = i：表示 x 的前 i 个字符全部删除。
   • dp[0][j] = j：表示 y 的前 j 个字符全部插入。
3. 动态规划计算：
   • 如果当前字符匹配，直接继承 dp[i-1][j-1]。
   • 否则，取 替换、删除、插入 的最小值并 +1。
4. 输出结果：dp[m][n] 即为最小操作次数。

该算法的时间复杂度为 O(mn)，适用于题目给定的约束条件（字符串长度 ≤ 1000）。