学步园

LCS问题即 longest common subsequence 最长公共子序列问题，也是经典的DP问题。

做这道题目的时候依旧是和做其他DP题目一样，按照步骤，先找到最优子结构，然后确定递归方程，然后就是填表和计算了。

given a sequence
X = 〈x₁,
x₂, ...,
x_m〉, we define the
ith prefix of
X, for
i = 0, 1, ..., m, as
X_i =
〈x₁,
x₂, ..., x_i〉. For example, if
X =
〈A,
B, C,
B, D,
A, B〉, then
X₄ =
〈A,
B, C,
B〉 and
X₀ is the empty sequence.

上面是定义一个序列的Xi前缀。

下面给出LCS的最优子结构

由此我们也可以得出下面的递归式

其中数组c[i,j]存的就是序列Xi与Yj的LCS长度。根据这个递归式就可以写代码了

#include <iostream>
#include <string>
using namespace std;

int c[100][100];
int b[100][100];

int LCS_Length(string x,string y)
{
	int m=x.length();
	int n=y.length();
	int i,j;

	//根据递归方程的第一种情况，先初始化数组c[][]
	for(i=1;i<=m;i++)
		c[i][0]=0;
	for(j=0;i<=n;i++)
		c[0][j]=0;

	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			//递归方程case 2
			if(x[i-1] == y[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;  //表示↖   
			}  
			else if(c[i-1][j] >= c[i][j-1])   //下面是递归方程case3
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;  //表示↑
			}
			else
			{
				c[i][j]=c[i][j-1];;
				b[i][j]=3;  //表示←
			}
		}
	return c[m][n];
}

//输出最优解
void Print_LCS(string X,int i,int j)
{
	if( (i == 0) || (j == 0) )
		return;
	if(b[i][j] == 1)
	{
		Print_LCS(X,i-1,j-1);
		cout<<X[i-1]<<" ";
	}
	else if(b[i][j] == 2)
		Print_LCS(X,i-1,j);
	else
		Print_LCS(X,i,j-1);
}

int main()
{
	string X,Y;
	while(cin>>X>>Y)
	{
		int p=LCS_Length(X,Y);
		cout<<"这两个字符串的LCS为："<<p<<endl;
		cout<<"该公共子序列为：";
		Print_LCS(X,X.length(),Y.length());
		cout<<endl;
	}
	return 0;
}

运行结果

ABCBDAB BDCABA
这两个字符串的LCS为：4
该公共子序列为：B C B A
EDFNGS ADASD
这两个字符串的LCS为：2
该公共子序列为：D S
KAYSPRINT JUSTDOIT
这两个字符串的LCS为：3
该公共子序列为：S I T
^Z
^Z
Press any key to continue

最后附上一张求解过后构造最优解时候的示意图，构造的是测试的第一个例子