NYOJ 36 最长公共子序列 【dp问题】

原题链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=36

思路：举个例子吧，序列 ********d 和****d 最长子序列=********和****的最长子序列+1；如果其中一个序列的d换成别的字母（不是d就行，假设k吧），最长子序列=max（********k和****的公共子序列，********和****d的公共子序列），明白了吧。。以下是代码。。

#include<stdio.h>
#include<string.h>
#define max 1001
int main()
{
	int a,b,c,n,m,s;
	scanf("%d",&s);
	while(s--)
	{
		int yi[max][max]={0,0};
		char ok1[1005];
		char ok2[1005];
		scanf("%s %s",ok1,ok2);
		m=strlen(ok2);
		n=strlen(ok1);
		for(a=0;a<n;a++)
		{
			for(b=0;b<m;b++)
			{
				if(ok1[a]==ok2[b])
				{yi[a+1][b+1]=yi[a][b]+1;}
				else
				{
					if(yi[a][b+1]>yi[a+1][b])
						yi[a+1][b+1]=yi[a][b+1];
					else
						yi[a+1][b+1]=yi[a+1][b];
				}
			}
		}
		printf("%d\n",yi[n][m]);
	}
}