P2758 编辑距离

题目

P2758 编辑距离

算法标签: 动态规划

思路

使用最小操作次数将$A$转化为$B$求最小操作次数, 设状态表示$f[i][j]$表示第一个字符串的前$i$个字符和第二个字符串的前$j$个字符相同的最小操作次数, 如何进行状态转移? 按照最后一步进行划分, 因为将字符串$A$转化为$B$有三种操作, 可以将集合划分为四类, 算法时间复杂度$O(n^2)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2010;

int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    string s1, s2;
    cin >> s1 >> s2;
    s1 = ' ' + s1;
    s2 = ' ' + s2;

    memset(f, 0x3f, sizeof f);

    for (int i = 0; i < s1.size(); ++i) f[i][0] = i;
    for (int i = 0; i < s2.size(); ++i) f[0][i] = i;

    for (int i = 1; i < s1.size(); ++i) {
   
        for (int j = 1; j < s2.size(); ++j) {
   
            if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1];
            else {
   
                f[i][j] = min({
   f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) + 1;
            }
        }
    }

    cout << f[s1.size() - 1][s2.size() - 1] << "\n";

    return 0;
}