f(i,j)
a的前i
个字母变成b的前j
需要的最少步骤
分别分析三种情况:
-
删除:假设已知
a
的前i-1
变成b
的前j
个字母的最小步骤,f[i][j] = f[i-1][j] + 1
-
增加:假设已知
a
的前i
变成b
的前j-1
个字母的最小步骤,
即假设a
的前i
个字母和b
的前j-1
个字母已经相同,f[i][j] = f[i][j-1] + 1
-
修改:假设已知
a
的前i-1
变成b
的前j-1
个字母的最小步骤,
即假设a
的前i+1
个字母和b
的前j-1
个字母已经相同,
若a[i] == b[j]
,则f[i][j] = f[i-1][j-1]
否则,f[i][j] = f[i-1][j-1] + 1
-
边界条件(真不知道大佬们怎么想到的aaa):当
a
是0个字母的时候,对于b[k],f[i][j] = k
同理,当b是0个字母的时候,对于a[k],f[i][j] = k
#include <iostream>
#include <cstring>
using namespace std;
const int n = 1010;
int N, M;
int f[n][n];
int dp(string a, string b)
{
// 边界
for(int i = 0; i <= M;i++) f[0][i] = i;
for(int i = 0; i <= N;i++) f[i][0] = i;
// 为了下标从1开始
a = '1' + a;
b = '2' + b;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
{
// 增 删
f[i][j] = min(f[i -1][j], f[i][j-1]) + 1;
// 改与不改
if(a[i] == b[j])
f[i][j] = min(f[i][j], f[i-1][j-1]);
else
f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
}
return f[N][M];
}
int main()
{
string a , b;
cin >> N >> a>> M >>b;
cout << dp(a, b);
return 0;
}