题目描述
902.最短编辑距离
给定两个字符串 AA 和 BB,现在要将 AA 经过若干操作变为 BB,可进行的操作有:
删除–将字符串 AA 中的某个字符删除。
插入–在字符串 AA 的某个位置插入某个字符。
替换–将字符串 AA 中的某个字符替换为另一个字符。
现在请你求出,将 AA 变为 BB 至少需要进行多少次操作。
样例
cin>>
10
AGTCTGACGC
11
AGTAAGTAGGC
cout<<
4
算法1
(dp) $O(n^2)$
首先dp继承上一任dp,其次分两种情况,如果相等不用+1,如果不等需要+1
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, dp[N][N];
char a[N], b[N];
int main(void){
cin >> n >> a + 1 >> m >> b + 1;
for(int i = 1; i <= n; i++) dp[i][0] = i;
for(int j = 1; j <= m; j++) dp[0][j] = j;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
}
cout << dp[n][m] << endl;
return 0;
}