通过LCS（最长公共子序列）和数学计算

可以大概证明结果等于两个字符串更长的一个减去最长公共子序列的长度

萌新也是刚学dp，请多多指教

这个LCS好像也有问题：按照原题的样例算出来是4

代码如下：

#include<iostream>
using namespace std;
string a,b;
int lena,lenb;
int f[2005][2005];
void dp(){
    for(int i=1;i<=lena;i++) f[i][0]=0;
    for(int i=1;i<=lenb;i++) f[0][i]=0;
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i][j-1],f[i-1][j]);
        }
    }
}
int main()
{
    cin>>a>>b;
    lena=a.size();lenb=b.size();
    dp();
    cout<<max(lena,lenb)-f[lena][lenb]<<endl;
    return 0;
}