（蓝桥杯）算法提高 最长公共子序列

问题描述

　　给定两个字符串，寻找这两个字串之间的最长公共子序列。

输入格式

　　输入两行，分别包含一个字符串，仅含有小写字母。

输出格式

　　最长公共子序列的长度。

样例输入

abcdgh
aedfhb

样例输出

3

样例说明

　　最长公共子序列为a，d，h。

数据规模和约定

　　字串长度1~1000。

最长公共子序列(longest common sequence)LCS

经典的动态规划问题，首先我们考虑下如果s1和s2的最后一个元素相等，那么s1和s2的LCS=s1减去最后一个元素和s2减去最后一个元素的LCS+1,但是如果最后一个元素不相等，那么s1和s2的LCS = s1减去最后一个元素与s2的LCS 与 s2减去最后一个元素与s1的LCS 中最大的那一个。

然后我们使用二维数组DP存放值。

注意此题不用写成递归，写成递归反而费时费力，因为它的下一个在前面已经出现过，直接可以算出来，用递归反而超时。

#include<iostream>
#include<cstdio>
#include<string>

using namespace std;

int dp[1005][1005];

int main()
{
	string s1,s2;
	cin>>s1>>s2;
	int len1=s1.size();
	int len2=s2.size();
	for(int i=1;i<=len1;i++){
		for(int j=1;j<=len2;j++){
			if(s1[i-1]==s2[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
				dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
			}
		}
	}	
	printf("%d\n",dp[s1.size()][s2.size()]);
	return 0;
}