http://acm.pku.edu.cn/JudgeOnline/problem?id=3356和最長公共子序列類似
如果s1[i]==s2[j] f[i][j] =min{不操作; 在i中刪除操作;在j中插入操作 }
否則 f[i][j]=min{改變; 在i中刪除操作;在j中插入操作 }
初始化的時候和最長公共子序列不同
Source Code
Problem: 3356 User: lnmm
Memory: 3992K Time: 31MS
Language: C++ Result: Accepted
Source Code
#include "stdio.h"
int f[1002][1002];
int min(int a,int b,int c)
{
int temp;
temp=a<=b?a:b;
return c<=temp?c:temp;
}
void main()
{ int i,j;
int len1,len2;
char str1[1002],str2[1002];
while(scanf("%d",&len1)!=EOF)
{
// scanf("%d",&len1);
scanf("%s",str1+1);
scanf("%d",&len2);
scanf("%s",str2+1);
for(i=0;i<=len1;i++)
f[i][0]=i;
for(j=0;j<=len2;j++)
f[0][j]=j;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(str1[i]==str2[j])
f[i][j]=min(f[i-1][j-1],f[i-1][j]+1,f[i][j-1]+1);
else f[i][j]=min(f[i-1][j-1]+1,f[i-1][j]+1,f[i][j-1]+1);
}
printf("%d\n",f[len1][len2]);
}
}