LCS / LIS 基础算法及路径保存

LCS（最长公共子序列,Longest Common Subsequence）:

已知两个字符串S ，T 求他们的公共子序列：

按照白书对于dp数组的定义

递推关系如下：

dp[ i+1 ][ j+1 ]=dp[ i ][ j ]+1 ( s[i]==t[j] )

dp[ i+1 ][ j+1 ]=max(dp[ i ][ j+1 ] , dp[ i+1 ][ j ] ) (其他)

自己理解下，不懂的去百度；

看了好多大神的博客，总结了以下代码：

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=2005;
string s,t;
int dp[MAX_N][MAX_N];     
int pre[MAX_N][MAX_N];   //标记路径 
vector<char> ans;        //保存路径 

void output(int x,int y){
	if(x==0||y==0) return ; //超出边界。dp数组是从[1,n],[1~n]来定义的 
    else if(pre[x][y]==1){      //pre=1,状态是从左上方转移过来的，往左上方找 
    	output(x-1,y-1);        //递归地往回找 
    	ans.push_back(s[x-1]);  //保存路径，这里我保存了数值，也可以保存下标，x-1。 
	} 
	else if(pre[x][y]==2){ //pre=2,状态是从正上方转移过来的，往正上方找 
		output(x-1,y); 
	} 
	else if(pre[x][y]==3){ //pre=3,状态是从左边转移过来的，往左边找 
		output(x,y-1);
	}
}


int main(){
	cin>>s>>t;
	int n=s.length(),m=t.length();          //以dp[i+1][j+1]为讨论对象
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s[i]==t[j]){
				dp[i+1][j+1]=dp[i][j]+1;    //从左上角转移过来  
				pre[i+1][j+1]=1;              
			}
			else if(dp[i][j+1]>dp[i+1][j]){ //正上方的大于左边的 
			    dp[i+1][j+1]=dp[i][j+1];    //从正上方转移过来 
			    pre[i+1][j+1]=2;
			}
			else{
				dp[i+1][j+1]=dp[i+1][j];    //左边的大于正上方的
				pre[i+1][j+1]=3;            //左边转移过来
			} 
		}
	}	
		cout<<dp[n][m]<<endl;               //输出LCS的长度
	
		output(n,m);
                for(int i=0;i<ans.size();i++){
        	cout<<ans[i]<<" ";              //输出路径 
		}                                    	
	 
	
	return 0;
}

参考来自大神：王小二的博客

pre数组和output函数是用来保存路径的，不需要的话直接去掉就行。

LIS(最长上升子序列，Longest Increasing Subsequence ):

求一个数列中的最长上升子序列：

递推关系1：

dp[ i ] :以a[ i ] 为结尾的最长上升子序列的长度：

以a[i]为结尾的上升子序列有两类：

1：只包含a[ i ]的子序列，元素个数为1 ，（一开始就对左右元素的dp值初始化为1）；

2：在满足j < i 并且 a[ j ] < a[ i ] 的以a[ j ]结尾,追加上a[ i ]得到的子序.

（1）O(n^2)复杂度解决方案：

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=2005;

int a[MAX_N];
int dp[MAX_N];
int pre[MAX_N];       //标记路径,记录前驱 
int max_pos = 0;      //最大位置 
vector<int> ans;      //保存路径 

void DFS(int pos){
   
    if(pre[pos]!=-1) {
    	DFS(pre[pos]);
        ans.push_back(a[pos]); 
	}
	else{
		ans.push_back(a[pos]); 
        return;
	}
}

int main()
{
    int n,i,j;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    int res = 0;  //最长上升子序列的长度 
    memset(pre,-1,sizeof(pre));
   
    for(i=0;i<n;i++){
    	dp[i]=1;
        for(j=0;j<i;j++){
            if(a[i]>a[j] && dp[i]<dp[j]+1){
                dp[i]=dp[j]+1;
                if (dp[i]>=res){
                    res=dp[i];  max_pos=i;
                    pre[i]=j;
                }
            }
        }
    }
    
    cout<<res<<endl;
    DFS(max_pos);
    for(int i=0;i<ans.size();i++) 
    cout<<ans[i]<<" ";

    return 0;
}

递推关系2：

（2）O(nlogn)复杂度解决方案：

dp[ i ] :长度为i+1的上升子序列中末尾元素的最小值（不存在即为INF）

这个dp数组的更新非常有意思，自己可以下去模拟一下，但是要注意，dp数组只能保存最长上升子序列的长度，而不能保存正确的子序列。

比如 1 3 5 2 ：dp数组最后保存的会是1 2 5 ，显然，这不是正确的顺序。

那么怎么保存路径呢？

传送门 (LIS路径还原)

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=2005;
const int INF=0x3f3f3f3f;
int a[MAX_N];
int dp[MAX_N];
int pre[MAX_N];   //标记路径,记录前驱 
int pos[MAX_N];   
vector<int> ans;  //保存路径 


void output(int pos){
    if(pre[pos]!=-1){
       output(pre[pos]);
    }
	ans.push_back(pos+1); 
}

int main(){
    int n;
    while(cin>>n&&n){
    	ans.clear();
        for(int i=0;i<n;i++){
    		cin>>a[i];
	    }
		fill(dp,dp+n,INF);
		pos[0]=-1;
		int i,now;
		for(i=0;i<n;++i){
		    now=lower_bound(dp,dp+n,a[i])-dp;
			dp[now]=a[i],pos[now]=i;
			if(now==0)
	            pre[i]=-1;
	        else
	            pre[i]=pos[now-1];
		}
	        int k=lower_bound(dp,dp+n,INF)-dp;
		 cout<<k<<endl;
	    	output(pos[k-1]);
	    	
	    	for(int i=0;i<ans.size();i++){
	    		if(i!=ans.size()-1)
	    		cout<<ans[i]<<" ";
	    		else 
	    		cout<<ans[i]<<endl;
			}
    
	}
}