> abcbdcab	bdcabc
> amnpnrmn	bnrpanm
> abcbdab		abcbdab
> abc		abacabc
> abacada		bcd
> abdecfg		acgbde
> dynamic		programming
> programming 	contest
> textbook	txtbokk
> abcfbc         	abfcab
> abcfbc		abfc
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
> 
> 
> answer：
> 5
> 4
> 7
> 3
> 3
> 4
> 3
> 2
> 6
> 4
> 4
> 0
> 200
> 
> 我的代码：
> #include <iostream>
> using namespace std;
> 
> #define maxn 1002
> 
> int f[maxn][maxn];
> char str1[maxn],str2[maxn];
> 
> int find(char &c,char str[],int n)
> {
> 	for(int i = n;i>=0;i--)
> 	{
> 		if(str[i]==c)
> 			return i;
> 	}
> 	return -1;
> }
> 
> //n1,n2指从有字母的位置
> int dp(int n1,int n2)
> {
> 	if(f[n1][n2]!=-1)
> 		return f[n1][n2];
> 
> 	int index = find(str1[n1],str2,n2);
> 	if(n1==0)
> 	{
> 		if(index==-1)//最后一个都不是
> 		{
> 			f[n1][n2]=0;
> 			return 0;
> 		}else{//最后一个是
> 			f[n1][n2]=1;
> 			return 1;
> 		}
> 	}else
> 	{
> 		if(index==-1)//去找下一个
> 		{
> 			f[n1][n2]=dp(n1-1,n2);
> 			return f[n1][n2];
> 		}else{//最后一个字母有出处，考虑要还是不要
> 			int a = dp(n1-1,n2);//不要
> 			int b = dp(n1-1,index-1);//要
> 			if(a>b+1)
> 				f[n1][n2]=a;
> 			else
> 				f[n1][n2]=b+1;
> 			return f[n1][n2];
> 		}
> 	}
> }
> 
> int main()
> {
> 	while (cin >> str1 >> str2)
> 	{
> 		int len1 = strlen(str1)-1;
> 		int len2 = strlen(str2)-1;
> 		memset(f,-1,sizeof(f));
> 		dp(len1,len2);
> 		printf("%d\n",f[len1][len2]);
> 		/*for(int i=0;i<=len1;i++)
> 		{
> 			for(int j=0;j<=len2;j++)
> 				printf("%d  ",f[i][j]);
> 			printf("\n");
> 		}*/
> 	}
> 	return 0;
> 
> }