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