核心:动态规划
状态的定义:f[i][j] 表示所有把a中的前i个字母 变成 b中前j个字母的集合的操作集合
属性:min
集合划分: 状态定义的是使原始a[1~i]和b[1~j]匹配,而不是使修改之后的a[1~i]和b[1~j]匹配。
1.删除:删除a[i],那就是要使a[i-1]匹配b[j] — f[i-1][j]+1
2.增加:增加a[i+1],让a[i+1]=b[j],那前提要使a[i]匹配b[j-1] —f[i][j-1]+1
3.修改:修改a[i],但是要首先判断a[i]是否=b[j],如果相等,就不用进行操作—f[i-1][j-1]+0
如果不相等,则进行修改,使得a[i]=b[j] — f[i-1][j-1]+1* 状态的定义:f[i][j] 表示所有把a中的前i个字母 变成 b中前j个字母的集合的操作集合
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
char a[N], b[N];
int f[N][N];
int main(){
int n,m;
cin>>n;
cin>>a+1;
cin>>m;
cin>>b+1;
//初始化边界
for(int i=1;i<=n;i++)
f[i][0]=i; //比如a有0个字符,b有i个字符,那么只有进行i次增加的操作
for(int i=1;i<=m;i++)
f[0][i]=i; //a有i个字符,b有0个字符,那么只有进行i次删除操作
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);
}
printf("%d",f[n][m]);
return 0;
}