子序列问题

LIS：Longest Increasing Subsequence，最长递增子序列
LCS：Longest Common Subsequence，最长公共子序列

一、最长上升子序列(LIS)

1、最长上升子序列的元素不一定相邻 2、最长上升子序列一定是原序列的子集。

1.O(n*n)
对于每一个i，枚举在i之前的每一个元素j，然后对于每一个dp[j],如果元素i大于元素j，那么就可以考虑继承，而最优解的得出则是依靠对于每一个继承而来的dp值，取max.

for(int i=1;i<=n;i++)
    {
        dp[i]=1;//对每一个元素来说，其本身就是一个最长上升子序列。维护一个dp数组，使得dp[i]表示以第i元素为结尾的最长上升子序列长度，那么对于每一个dp[i]而言，初始值即为1
        for(int j=1;j<i;j++)//枚举i之前的每一个j 
        	if(data[j]<data[i] && dp[i]<dp[j]+1)//data存储原序列
        		dp[i]=dp[j]+1;
    }

最后dp[n]即为所求答案
2.O(nlogn)
将原来的dp数组的存储内容由数值换成该序列中，上升子序列长度为i的上升子序列的最小末尾数值。我们当前的上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以更方便地加入到序列中。

int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=0x7fffffff;
        //初始值要设为INF
        /*原因很简单，每遇到一个新的元素时，就跟已经记录的f数组当前所记录的最长
        上升子序列的末尾元素相比较：如果小于此元素，那么就不断向前找，直到找到
        一个刚好比它大的元素，替换；反之如果大于，那么填到末尾元素的下一个q，INF
                就是为了方便向后替换啊！*/ 
    }
    f[1]=a[1];
    int len=1;//通过记录f数组的有效位数，求得个数 
    /*因为上文中所提到我们有可能要不断向前寻找，
    所以可以采用二分查找的策略，这便是将时间复杂
    度降成nlogn级别的关键因素。*/ 
    for(int i=2;i<=n;i++)
    {
        int l=0,r=len,mid;
        if(a[i]>f[len])f[++len]=a[i];
        //如果刚好大于末尾，暂时向后顺次填充 
        else 
        {
        while(l<r)
        {   
            mid=(l+r)/2;
            if(f[mid]>a[i])r=mid;/*如果仍然小于之前所记录的最小末尾，那么不断向前寻找(因为是最长上升子序列，所以f数组必然满足单调)*/
            else l=mid+1; 
        }
        f[l]=min(a[i],f[l]);//更新最小末尾 
        }
    }
    cout<<len;

3.输出序列O(n*n)
记录前驱，然后递归输出（也可以用栈）

#include <iostream>
using namespace std;
const int MAXN = 1000 + 10;
int n, data[MAXN];
int dp[MAXN]; 
int from[MAXN]; 
void output(int x)
{
    if(!x)return;
    output(from[x]);
    cout<<data[x]<<" ";//迭代输出 
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>data[i];
    // DP
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        from[i]=0;
        for(int j=1;j<i;j++)
        if(data[j]<data[i] && dp[i]<dp[j]+1)
        {
            dp[i]=dp[j]+1;
            from[i]=j;//逐个记录前驱 
        }
    }

    int ans=dp[1], pos=1;
    for(int i=1;i<=n;i++)
        if(ans<dp[i])
        {
            ans=dp[i];
            pos=i;//由于需要递归输出所以要记录最长上升子序列的最后一个元素，来不断回溯出路径来 
        }
    cout<<ans<<endl;
    output(pos);
    return 0;
}

二、最长公共子序列(LCS)

用dp[i][j]来表示第一个串的前i位，第二个串的前j位的LCS的长度
状态转移方程

如果当前的A1[i]和A2[j]相同（即是有新的公共元素）那么

dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);

2.如果不相同（即无法更新公共元素），考虑继承：

dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

#include<iostream>
using namespace std;
int dp[1001][1001],a1[2001],a2[2001],n,m;
int main()
{
    //dp[i][j]表示两个串从头开始，直到第一个串的第i位 
    //和第二个串的第j位最多有多少个公共子元素 
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	scanf("%d",&a1[i]);
    for(int i=1;i<=m;i++)
    	scanf("%d",&a2[i]);
    for(int i=1;i<=n;i++)
     	for(int j=1;j<=m;j++)
      	{
        	if(a1[i]==a2[j])
        		dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        	else
        		dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    cout<<dp[n][m];
}