//1298

#include <iostream>

#include <cstring>

using namespace std;

string s1,s2;

int t;

int getedit(string s1,string s2){

   int f[2001][2001];

   memset(f,0,sizeof(f));

   //处理边界

   for(int i=1;i<=s1.size();i++) f[i][0]=i;

   for(int i=1;i<=s2.size();i++) f[0][i]=i;

   //填表

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

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

           if(s1[i-1]==s2[j-1]) 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;

       }

   }

   return f[s1.size()][s2.size()];

}

int main(){

   cin>>t;

   while(t--){

       cin>>s1>>s2;

       cout<<getedit(s1,s2)<<endl;

   }

   return 0;

}

//区域DP：最长回文子串

string s;

int getmaxlongstr(string s){

   vector<vector<bool>> f(s.size()+1,vector<bool>(s.size()+1,false));

   int maxl=0;

   string maxstr="";

   for(int len=0;len<s.size();len++){

       for(int i=0;i+len<s.size();i++){

           int j=i+len;

           if(len==0) f[i][j]=true;

           else if(len==1) f[i][j]=(s[i]==s[j]);

           else f[i][j]=(s[i]==s[j])&&(f[i+1][j-1]);

           if(f[i][j]&&maxl<len+1){

               maxl=len+1;

               maxstr=s.substr(i,len+1);

           }

       }

   }

   return maxl;//maxstr

}

作业：

1、洛谷P1210

2、估分

后面课程内容我们先学习动态规划系列知识，如果进入复赛，则开始复赛集训。