题目描述

模板题，最短编辑距离，动态规划

#include<iostream>
#include<cstring>

using namespace std;
int n;
const int N=1010;
int f[N][N];
int main(){
    cin>>n;string s1,s2;

    while(n--){
        s1="0";s2="0";
        string a,b;
        cin>>a>>b; s1+=a; s2+=b;
        //初始化
        for(int i=0;i<s1.size();i++)f[i][0]=i;
        for(int i=0;i<s2.size();i++)f[0][i]=i;

        for(int i=1;i<s1.size();i++){
            for(int j=1;j<s2.size();j++){

                f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
                //f[i-1][j]表示s1前i-1个字符和s2前j个字符匹配，删除s1第i个字符
                //f[i][j-1]表示s1前i个字符和s2前j-1个字符匹配，删除s2第j个字符

                if(s1[i]==s2[j])f[i][j]=min(f[i][j],f[i-1][j-1]);//s1[i]=s2[j],不需要做任何操作

                else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//表示修改字符，s1的第i个字符或s2的第j个字符皆可
            }
        }
        cout<<f[s1.size()-1][s2.size()-1]<<endl;

    }


    return 0;
}