算法设计与分析——最长公共子序列

运用了动态规划原理

若a[i]=b[j]，L[i,j]=L[i-1,j-1]+1。

若a[i]!=b[j]，L[i,j]=max{L[i,j-1],L[i-1,j]}。

代码如下：

#include
using namespace std;

int main()
{
    int L[100][100];
    char a[5]={'B','D','C','A'};
    char b[5]={'A','B','C','B'};
    for(int i=0;i<=4;i++)
    {
        L[i][0]=0;
    }
    for(int i=0;i<=4;i++)
    {
        L[0][i]=0;
    }
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            if(a[i]==b[j])
            {
                L[i][j]=L[i-1][j-1]+1;
            }
            else
            {
                L[i][j]=max(L[i-1][j],L[i][j-1]);
            }
        }
    }
    cout<