想了挺久到底第一篇在这儿的博客写什么好，刚好这两天又一次看到动态规划的LCS算法觉得还是有点意思的，就拿来写了写，第一篇博客就发它吧。
#include<iostream>
#include<iomanip>
using namespace std;
//tag标志，0为左斜上，1取左，2取上;count为最长公共子序列计数
//计算最长公共子序列长度
void LCS_Length(char *X, char *Y, int *count[],int *tag[],int length_X, int length_Y)
{
//第一排第一列全部是0
for (int i = ; i < length_X+; i++)
{
count[i][] = ;
}
for (int i = ; i < length_Y+; i++)
{
count[][i] = ;
} for (int i = ; i <= length_X; i++)
{
for (int j = ; j <= length_Y; j++)
{
if (X[i-] == Y[j - ])
{
count[i][j] = count[i-][j-]+;
tag[i][j] = ;
}
//否则取较大的值
else if(count[i-][j] > count[i][j-])
{
count[i][j] = count[i-][j];
tag[i][j] = ;
}
else
{
count[i][j] = count[i][j-];
tag[i][j] = ;
}
}
}
}
//打印最长公共子序列元素
void Print_LCS(int *tag[],char *X,int Length_X, int Length_Y)
{
if (Length_X == || Length_Y == )
{
return ;
}
int i = Length_X, j = Length_Y;
if (tag[i][j] == )
{
cout<<X[i-]<<setw();
Print_LCS(tag,X,i-,j-);
}
else if(tag[i][j] == )
{
Print_LCS(tag,X,i-,j);
}
else
{
Print_LCS(tag,X,i,j-);
}
} int main()
{
//先人为设置两个序列
char *X = "BDCABA";
char *Y = "ABCBDA";
int *count[];
for (int i = ; i < ; i++)
{
count[i] = new int[]; //因为第一行第一列全为0，所以总共七行七列
}
int *tag[];
for (int i = ; i < ; i++)
{
tag[i] = new int[];
}
LCS_Length(X,Y,count,tag,strlen(X),strlen(Y));
cout<<"最大子序列数为"<<count[][]<<endl;
/****************************************
for(int i= 0; i <7; i++)
{
for (int j = 0; j < 7; j++)
{
cout<<count[i][j]<<setw(3);
}
cout<<endl;
}
*****************************************/
Print_LCS(tag,X,strlen(X),strlen(Y));
cout<<endl;
return ;
}
主要函数有两个，一个函数是做出保存最长公共子序列的元素个数的矩阵，这里给出的示例中，两个字符串都各6个字符，所以给出的是7行7列矩阵（第一行第一列全为零）。
另外一个函数即为打印函数，从矩阵右下角一位开始遍历到[0][0]位，凡是遇到tag[i][j]标志为0则将该位的字符打印出来。算法比较简单易懂，具体可以参考《算法导论》。
下面补充说一个问题：二维指针到底怎么用。比如前面的二维数组初始化，如果我希望能够通过字符串的长度来给我的二维数组定义大小，而不是用常数来指定，使得我们可以通过strlen()函数来定义长度，那么就要用到二维指针。
注意：int *Arr[strlen(str)];这种声明方式是不正确的，编译器会提示错误，数组的声明必须使用常量。下面给出正确的示例：
/***********************************************
//华丽丽的分割线--------------------------------
二维指针到底怎么用
int *(*ptr) = new int*[strlen(X)];
for (int i = 0; i < strlen(X); i++)
{
ptr[i] = new int[strlen(X)];
}
ptr[2][3] = 0;
cout<<ptr[2][3]<<endl;
**********************************************/
