输入输出样例
输入样例输出样例
sfdqxbw4
gfdgw
看见求最优解,首先想到dp;
然后发现好像和最长公共子序列有关;
理性分析
loading......
令dp[i][j]为a1...ai和b1...bj的匹配最小改动长度
则如果ai==bj
dp[i][jj=dp[i-1][j-1];
如果不匹配
则可以选ai或bj或 (我全都要!!!)
dp[i][j]=min( min(dp[i][j-1],dp[i-1][j]) ,dp[i-1][j-1]) +1;
好了;
别忘了赋初值;
骚代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
char a[2010],b[2010];
int a1[2010],b1[2010];
int lena,lenb;
int dp[2010][2010];
int main()
{
freopen("in","r",stdin);
scanf("%s",a);
printf("%s\n",a);
scanf("%s",b);
printf("%s\n",b);
lena=strlen(a);
lenb=strlen(b);
for(int i=1;i<=lena;++i) dp[i][0]=i;
for(int i=1;i<=lenb;++i) dp[0][i]=i;
for(int i=1;i<=lena;++i)
{
for(int j=1;j<=lenb;++j)
{
if(a[i-1]==b[j-1])
{
dp[i][j]=dp[i-1][j-1];
continue;
}
dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
}
}
printf("%d",dp[lena][lenb]);
}
来源: http://www.bubuko.com/infodetail-2462721.html