2569360_ac_15ms_3992k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int dp[1001][1001];

int main()
{
	int i, j, la, lb;
	char a[1001], b[1001];

	while(scanf("%d%s%d%s",&la,a,&lb,b)==4)
	{
		dp[0][0] = 0;
		for(i = 1; i <= la; i++)
			dp[i][0] = dp[i-1][0]+1;
		for(i = 1; i <= lb; i++)
			dp[0][i] = dp[0][i-1]+1;
		for(i = 1; i <= la; i++)
			for(j = 1; j <= lb; j++)
			{
				dp[i][j] = dp[i-1][j-1]+1-(a[i-1]==b[j-1]);
				if(dp[i][j]>dp[i-1][j]+1)
					dp[i][j] = dp[i-1][j]+1;
				if(dp[i][j]>dp[i][j-1]+1)
					dp[i][j] = dp[i][j-1]+1;
			}
		printf("%d\n",dp[la][lb]);
	}
	return 0;
}