LCS（最长公共子序列）

模板题：
http://acm.hdu.edu.cn/showproblem.php?pid=1159
Common Subsequence（最长公共子序列）
题意：
求两端字符串的最长公共子序列的长度

通过二维数组保存每段LCS的长度，则状态转移方程为：

实现过程：
以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。

c[i,j]的定义，记录的LCS的长度值。
通过递归公式填入表中，如果横竖（i,j）对应的两个元素相等，该格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化该表：

S1的元素3 与 S2的元素3 相等，所以 c[2,1] = c[1,0] + 1。

S1的元素3 与 S2的元素5 不等，c[2,2] =max(c[1,2],c[2,1])。

中间填入规则不变，以此类推：

常规版本：
时间复杂度为O(n^2)
空间复杂度为O(n^2）
代码实现：

#include<bits\stdc++.h>
using namespace std;
int dp[2100][2100];
int main()
{
	string s,s1;
	while(cin>>s>>s1)
	{
		memset(dp,0,sizeof(dp));
		int a=s.size(),b=s1.size();
		for(int i=1;i<=a;i++)
		{
			for(int j=1;j<=b;j++)
			{
				if(s[i-1]==s1[j-1])
				dp[i][j]=dp[i-1][j-1]+1;
				else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
		cout<<dp[a][b]<<endl;
	}
	return 0;
}

空间优化版本：
由于每一次的改变只与dp[i-1][j-1]，dp[i][j-1]和dp[i-1][j]三个有关则可以通过滚动数组来保存数据，且数组基数最大为2，则可以选择模2。
时间复杂度为O(n^2)
空间复杂度为O(n）
代码实现：

#include<bits\stdc++.h>
using namespace std;
int dp[10][2100];
int main()
{
	string s,s1;
	while(cin>>s>>s1)
	{
		memset(dp,0,sizeof(dp));
		int a=s.size(),b=s1.size();
		for(int i=1;i<=a;i++)
		{
			for(int j=1;j<=b;j++)
			{
				if(s[i-1]==s1[j-1])
				{
					dp[i%2][j]=dp[(i-1)%2][j-1]+1;
				}
				else
				{
					dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
				}
			}
		}
		cout<<dp[a%2][b]<<endl;
	}
	return 0;
}

LIS（最长上升子序列）

模板题：
https://vjudge.net/problem/POJ-2533

思路：
设dp[i]表示：从左至右扫描以ar[i]结尾的序列，就可以得到最长上升子序列。
dp(i)的递推公式如下：
1)dp(i)=1 当i=1;
2)dp(i)=max{dp(j)+1} 当ar[i]>ar[j],j大于等于1且小于i,i>1;
3)dp(i)=1 当对任意j,(j大于等于1且小于i),都有ar[i]<=ar[j];

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1100;
int dp[N],ar[N];
int main()
{
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&ar[i]);
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		dp[i]=1;
		for(int j=1;j<i;j++)
		{
			if(ar[i]>ar[j])
			{
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		ans=max(dp[i],ans);
	}
	cout<<ans<<endl;
	return 0;
}

优化练习：
https://www.luogu.com.cn/problem/AT2827（需要用DP加二分）不然要超时和爆空间

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+100;
int s[N],ar[N];
int main()
{
	int n,ans=0,tot=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&ar[i]);
	}
	memset(s,0,sizeof(s));
	s[++tot]=ar[1];
	for(int i=1;i<=n;i++)
	{
		if(ar[i]>s[tot])
		{
			s[++tot]=ar[i];
		}
		else
		{
			int temp=lower_bound(s+1,s+1+tot,ar[i])-s;
			s[temp]=ar[i];
		}
	}
	cout<<tot<<endl;
	return 0;
}

链接: LIS和LCS的题库.