所谓dp状态的转移就是分类讨论
这道题我们可以分为3种情况去讨论
1.插入操作
联系dp状态的定义,在i插入后使a[1~i]和b[1~j]匹配,就说明原来的a[1~i]与b[1~j-1]匹配
2.删除操作
删除i这个位置,说明原来的a[1~i-1]与b[1~j]匹配
3.替换操作
把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配
那么修改这一位之前,a[1~(i-1)]应该与b[1~(j-1)]匹配
f[i-1][j-1] + 1
但是如果本来a[i]与b[j]这一位上就相等,那么不用改,即
f[i-1][j-1] + 0
需要注意的我都写在代码的注释里了
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
int f[N][N];
int n,m;
char a[N],b[N];
int main()
{
cin>>n>> (a+1)>> m>> (b+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=0x3f3f3f3f;//我们初始化的时候要将情况考虑清楚,比如f[0][0]对应的操作数应该是0,
//而不能初始化成0x3f3f3f3f,我们初始化成正无穷,只是为了让这种情况在没有计算的时候不合法。
//一定要联系dp状态的定义去初始化
for(int i=1;i<=n;i++)
f[i][0]=i;//删除操作
for(int i=1;i<=m;i++)
f[0][i]=i;//插入操作
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[i][j]=min(min(f[i][j],f[i-1][j]+1),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);
}
// for(int i=1;i<=n;i++)
// cout<<a[i]<<' ';
// puts(" ");
// for(int j=1;j<=m;j++)
// cout<<b[j]<<' ';
cout<<f[n][m];
}