给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：
删除–将字符串A中的某个字符删除。
插入–在字符串A的某个位置插入某个字符。
替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将A变为B至少需要进行多少次操作。
输入格式
第一行包含整数n，表示字符串A的长度。
第二行包含一个长度为n的字符串A。
第三行包含整数m，表示字符串B的长度。
第四行包含一个长度为m的字符串B。
字符串中均只包含小写字母。
输出格式
输出一个整数，表示最少操作次数。
数据范围
1≤n,m≤1000
输入样例：
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例：
4
/****
dP 题目分析
- 状态f[i,j]表示（把a串（1~i)变成b串（1~j)最少步数
- 比较（a[i],b[j])时
f[i-1][j]表示a串删除a[i],a[1~i-1]与j[1~j]匹配的步数
f[i][j-1]表示a串插入一个字符b[j]与b[j]相匹配 - 属性：min
- 状态计算：
当a[i]==b[j]时，f[i][j] ==f[i-1][j-1]//相等的话，就是前[i-1,j-1]需要的步数
不相等时f[i][j] = min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1
***/
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
`using namespace std;
int f[1010][1010];
int main()
{
int n,m;
char s1[1010],s2[1010];
cin >> n >> (s1+1);
cin >> m >> (s2+1);
for(int i=0;i<=n;i++)f[i][0]=i;//减去，b串为空，匹配的话只能把a全部删掉
for(int i=0;i<=m;i++)f[0][i] = i;//加上，a为空串，匹配的话只能把a一个个加上
for(int i=1;i<=n;i++)
{
for(int j =1;j<=m;j++)
{
if(s1[i]==s2[j])
{
f[i][j]=f[i-1][j-1];
}
else
{
f[i][j] =min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
}
}
}
cout << f[n][m]<<endl;
return 0;
}```
