题目传送门

题目大意

给定两个字符串 A 和 B，每次可以对 A 进行如下三种操作之一：

  1. 删除一个字符；
  2. 插入一个字符；
  3. 将一个字符改为另一个字符。

求最少需要多少次操作能将 A 变成 B。

思路分析

本题是经典的莱文斯坦(Levenshtein Distance)问题。我们用动态规划解决。

状态定义

设 f[i][j] 表示将 A 的前 i 个字符变成 B 的前 j 个字符的最少操作次数。

状态转移

  • 删除：f[i-1][j] + 1，即删除 A 的第 i 个字符。
  • 插入：f[i][j-1] + 1，即在 A 末尾插入 B 的第 j 个字符。
  • 替换/不变：f[i-1][j-1] + \text{cost}，其中 \text{cost}=0 若 A[i]=B[j]，否则 \text{cost}=1。

综合起来，状态转移方程为：

f[i][j] = \min \left\{ \begin{array}{l} f[i-1][j] + 1 \\ f[i][j-1] + 1 \\ f[i-1][j-1] + \text{cost} \end{array} \right.

边界条件

  • f[0][j] = j，即 A 为空时，需要插入 j 个字符。
  • f[i][0] = i，即 B 为空时，需要删除 i 个字符。

代码实现

#include <bits/stdc++.h>
using namespace std;
int f[2005][2005];
string A, B;

int main() {
    cin >> A >> B;
    int lena = A.length(), lenb = B.length();
    // 下标从1开始，方便处理
    A = " " + A;
    B = " " + B;
    // 初始化边界
    for (int i = 0; i <= lena; i++) f[i][0] = i;
    for (int j = 0; j <= lenb; j++) f[0][j] = j;
    // 状态转移
    for (int i = 1; i <= lena; i++) {
        for (int j = 1; j <= lenb; j++) {
            int cost = (A[i] == B[j] ? 0 : 1);
            f[i][j] = min({f[i-1][j] + 1, f[i][j-1] + 1, f[i-1][j-1] + cost});
        }
    }
    cout << f[lena][lenb];
    return 0;
}

复杂度分析

  • 时间复杂度：\mathcal{O}(|A| \times |B|)
  • 空间复杂度：\mathcal{O}(|A| \times |B|)