题目描述

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

1·删除–将字符串 A 中的某个字符删除。
2·插入–在字符串 A 的某个位置插入某个字符。
3·替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。

样例

输入样例：
10 
AGTCTGACGC
11 
AGTAAGTAGGC
输出样例：
4

注意f[i][j]的初始化

#include<iostream>
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int main()
{
    int n,m;
    scanf("%d%s%d%s",&n,a+1,&m,b+1);
    for(int i=1;i<=n;i++)f[i][0]=i;
    for(int j=1;j<=m;j++)f[0][j]=j;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(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]+1);
            else f[i][j]=min(f[i][j],f[i-1][j-1]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}