最长公共子序列的长度（动态规划）解决方案

最长公共子序列的长度（动态规划）
给定X = 3, 0, 3, 8, 4, 4
　　Y= 4, 3, 8, 3, 0, 4
求X和Y的最长公共子序列的长度。
------解决方案--------------------
int len[8][6] = {0};  //记录序列1的 i 和序列2的 j 的最长公共子序列的长度
int flag[8][6] = {0}; //记录在i和j处的选择,为后面输出最长子序列
 
int LCS()
{
    int i, j;
     
    for(i=1; i<m; i++)
    {
        for(j=1; j<n; j++)
        {
            if(X[i] == Y[j])
            {
                len[i][j] = len[i-1][j-1] + 1;
                flag[i][j] = 0;    
            }
            else if(len[i-1][j] >= len[i][j-1])
            {
                len[i][j] = len[i-1][j];
                flag[i][j] = 1;  
            }
            else
            {
                len[i][j] = len[i][j-1];
                flag[i][j] = 2;
            }
        }       
    }
    return len[m-1][n-1];
}
 
void printLCS(int i, int j)
{
    if(i==0 
------解决方案--------------------
 j==0)
        return;
    if(flag[i][j] == 0)
    {
        printLCS(i-1, j-1);
        printf("%c ", X[i]);
    }
    else
    {
        if(flag[i][j] == 1)
            printLCS(i-1, j);
        else
            printLCS(i, j-1);
    }
}
 
int main()
{
    printf("Longest Common Sequence Length: %d\n", LCS());
    printLCS(m-1, n-1);
    printf("\n");
    return 0;
}
------解决方案--------------------
DP主要就是一个递推公式。
其实现还是比较简单的，填表法，需要记录解的过程，这样才能在之后找到解。

#include <iostream>

#include <string>

#include <stack>

using namespace std;


/*

DP的核心公式：

if xi = yj:

  LCS(xi,yj)=LCS(xi-1,yj-1)+1;

else  

  LCS(xi,yj)=max(LCS(xi-1,yj),LCS(xi,yj-1)).

*/


int LCS_DP( string x, string y )

{

	int xlen=x.size();

	int ylen=y.size();

	//int *lcs = new int[(xlen+1)*(ylen+1)]();

	int **lcs = new int*[xlen+1];

	int **path = new int*[xlen+1];


	for( int i=0; i<=xlen; i++){

		lcs[i] = new int[ylen+1]();

		path[i] = new int[ylen+1]();

	}


	for( int k=1; k<=xlen+ylen;k++){

		for( int i=1; i<=xlen; i++){

			for( int j=1; j<=k-i&&j<=ylen; j++){

				if(x[i-1]==y[j-1]){

					lcs[i][j] = lcs[i-1][j-1]+1;

					path[i][j] = 1;					//1表示两个字符相等

				}

				else{

					int a=lcs[i-1][j];

					int b=lcs[i][j-1];

					lcs[i][j] = a>b?a:b;

					path[i][j] = a>b?2:3;           //2表示来自y，3表示来自x

				}

			}

		}

	}


	stack<char> stk;

	for( int i=xlen,j=ylen; i>0&&j>0; )

	{

		if( path[i][j] == 1 ){

			stk.push( x[i-1] );

			i--;j--;

		}

		if( path[i][j] == 2 ){

			i--;

		}

		if( path[i][j] == 3 ){

			j--;

		}

	}


	cout <<"The Longest Common Sequence Length: " <<lcs[xlen][ylen]<<endl;

	cout <<"The Longest Common Sequence is:"<<endl;