【DP温习4—LCS】HDU1159——Common Subsequence

【DP复习4—LCS】HDU1159——Common Subsequence

题目：点击打开链接

没什么多说的，LCS问题盲打过，但我CE了两次，因为把I和J搞混了。。另外注意LCS是中间可以有间隔的，KMP则没有。另外别忘了前两天博客中曾经提到的二分法。

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int max(int a,int b)
{
	return a>b?a:b;
}

int dp[3400][3400];
int main()
{
	string a,b;
	while(cin>>a>>b)
	{
		int as=a.size();
		int bs=b.size();
		for(int i=0;i<as;i++)
		{
			for(int j=0;j<bs;j++)
			{
				dp[i][j]=0;
			}
		}
		//dp[0][0]=1;
		
		for(int i=0;i<=as;i++)
		{
			for(int j=0;j<=bs;j++)
			{
				if(a[i]==b[j])
				{
					dp[i+1][j+1]=dp[i][j]+1;
				}
				else
				{
					dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
				}
			}
		}
		cout<<dp[as][bs]<<endl;
		
	}
	
	return 0;
}