***************************************转载请注明出处：http://blog.csdn.net/lttree********************************************

第二章：动态规划

<span style="font-family:Comic Sans MS;font-size:12px;">#include <iostream>
using namespace std;
const int M = 7;
const int N = 6;

// 求最长公共子序列函数
void LCSLength( int m , int n ,char* x ,char* y,int** c,int** b)
{
    int i,j;
    // 数组边界设置为0
    for( i = 1 ; i <= m ; ++i ) c[i][0] = 0;
    for( i = 1 ; i <= n ; ++i ) c[0][i] = 0;

    // 挨个比较
    for( i = 1 ; i <= m ; ++i )
        for( j = 1 ; j <= n ; ++j ) {
            // 如果 相应位置 字符相等，则最长子序列在之前的基础上+1，并且b数组存储标记1
            if( x[i] == y[j] )  {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;
            }
            // 如果 相应位置 字符不同，则查询横向和纵向哪个子序列长度最长，并且b数组存储相应标记
            else if( c[i-1][j] >= c[i][j-1] )   {
                c[i][j] = c[i-1][j];
                b[i][j] = 2;
            }
            else    {
                c[i][j] = c[i][j-1];
                b[i][j] = 3;
            }
        }
}

// 输出函数
void output(char *s,int n)
{
    for(int i=1; i<=n; i++)
    {
        cout<<s[i]<<" ";
    }
    cout<<endl;
}

// 输出最长公共子序列函数
void LCS( int i ,int j ,char* x,int** b )
{
    if( i == 0 || j == 0 )  return;
    if( b[i][j] == 1 )  {
        LCS(i-1,j-1,x,b);
        cout<<x[i];
    }
    else if( b[i][j] == 2 )
        LCS(i-1,j,x,b);
    else
        LCS(i,j-1,x,b);
}

int main()
{
    char x[] = {' ','A','B','C','B','D','A','B'};
    char y[] = {' ','B','D','C','A','B','A'};

    int **c = new int *[M+1];
    int **b = new int *[M+1];
    for(int i=0;i<=M;i++)
    {
        c[i] = new int[N+1];
        b[i] = new int[N+1];
    }

    cout<<"序列X："<<endl;
    output(x,M);
    cout<<"序列Y："<<endl;
    output(y,N);

    LCSLength(M,N,x,y,c,b);

    cout<<"序列X、Y最长公共子序列长度为："<<c[M][N]<<endl;
    cout<<"序列X、Y最长公共子序列为："<<endl;
    LCS(M,N,x,b);
    cout<<endl;
    return 0;
}</span>

算法重拾之路——最长公共子序列(LCS)