题目描述
给定两个字符串 A 和 B,现在要将 A 经过若干操作变为 B,可进行的操作有:
1 删除–将字符串 A 中的某个字符删除。
2 插入–在字符串 A 的某个位置插入某个字符。
3 替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出,将 A 变为 B 至少需要进行多少次操作。
输入格式
第一行包含整数 n,表示字符串 A 的长度。
第二行包含一个长度为 n 的字符串 A。
第三行包含整数 m,表示字符串 B 的长度。
第四行包含一个长度为 m 的字符串 B。
字符串中均只包含大写字母。
输出格式
输出一个整数,表示最少操作次数。
数据范围
1≤n,m≤1000
样例
10
AGTCTGACGC
11
AGTAAGTAGGC
4
算法1
(动态规划) $O(n^2)$
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 1005;
char a[N], b[N];
int f[N][N]; //表示所有使得a[1,...i..n]变成b[1,....j,...m]的所有操作次数
int n, m;
int main()
{
scanf("%d%s", &n, a + 1);
scanf("%d%s", &m, b + 1);
// 初始化a, b任意一个为0的情况
for (int i = 0; i <= m; i ++ ) f[0][i] = i; // a为0, 增加a
for (int i = 0; i <= n; i ++ ) f[i][0] = i; // b为0, 删除a
for (int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
printf("%d\n", f[n][m]);
return 0;
}