最长公共子序列（不是子串）hdu1159

考的是最长公共子序列+dp；
子序列不是子串，不是子串！不连续也可以，只要a[]和b[]串共有的元素即可。
最主要的是此类问题用dp解决。
注意状态转移方程，dp[i][j]=dp[i-1][j-1]-1;dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
求最长公共子序列，用一个二维数组dp[i][j]保存a[]和b[]的最长公共子序列.
如果a[i]==b[j],则dp[i][j]=dp[i-1][j-1]+1如果a[i]!=b[j],则有dp[i][j]=max(dp[i-1][j],dp[i][j-1]),由上一结果的最大值继承而来。
代码：

 #include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1100][1100];
int main()
{
	char a[1100],b[1100];
	int l1,l2,i,j;
	while(~scanf("%s %s",a,b))
	{
		memset(dp,0,sizeof(dp));
		l1=strlen(a),l2=strlen(b);
		for (i=1;i<=l1;i++)
		{
			for (j=1;j<=l2;j++)
			{
				if (a[i-1]==b[j-1])
				dp[i][j]=dp[i-1][j-1]+1;//
				else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//
			}
		}
		printf("%d
",dp[l1][l2]);
	}
	return 0;
}