動态規劃經典問題----最長公共子序列

給定兩個序列 X={x1，x2，x3，…，xm}和 Y={y1，y2，y3，…，yn}，找出 X 和 Y 的一個

最長的公共子序列。

例如：X=（A，B，C，B，A，D，B），Y=（B，C，B，A，A，C），那麼最長公共子

序列是 B，C，B，A；

分析：由于如果直接暴力破解，時間複雜度是我們避之不及的爆炸性指數。可以用動态規劃分析其最優子結構，然後建立最優值的遞歸式，有點類似于我們中學所學數列中的通項，但還是有點差別。

（一）假設：已知Zk={z1,z2,z3.......zk}是X={x1，x2，x3，…，xm}和 Y={y1，y2，y3，…，yn}的最優子結構

①：當Xm=Yn=Zk時，Z={z1,z2.....zk-1}時，Zk-1是Xm-1和 Yn-1的最長公共子序列。

反證法：如果Zk-1不是Xm-1和 Yn-1的最長公共子序列。則存在一個序列M為Xm-1和 Yn-1的最長公共子序列，則M>Zk-1，那麼在三序列後面加上Xm=Yn=Zk,因為M+Zk>Zk-1+Zk，則M+Zk為Xm和 Yn的最長公共子序列，這與假設沖突，是以Zk-1就是Xm-1和 Yn-1的最長公共子序列。

②當Xm≠Yn，Xm≠Zk時，我們可以先把Xm去掉，則Zk是Xm-1和Yn的最長公共子序列。

反證法：如果Zk不是Xm-1和Yn的最長公共子序列。則存在一個序列M是Xm-1和Yn的最長公共子序列，是以M>Z，當把Xm加到Xm-1處時，由于M>Z，則M是Xm和Yn的最長公共子序列。這與假設沖突。

③當Xm≠Yn，Yn≠Zk時，同②證法一樣，Zk是Xm和Yn-1的最長公共子序列。

這說明這題具有最優子結構的性質，是典型的D題。

（二） 建立最優值遞歸式

用C[i][j]來存儲最優值

①：當Xm=Yn=Zk時，C[i][j]=C[i1][j-1]+1;

②：當Xm≠Yn時，我們隻需要比較Xm-1和Yn與Xm和Yn-1的最長公共子序列哪個更長；即：C[i][j]=max{C[i-1][j],C[i][j-1]};

當i=j=0時，C[i][j]=0;

(三)向上計算最優解

由于最優值隻是得到了一個最長的一個數值，并不知道序列是什麼，假設猜C[m][n]=5，我們知道這個最長公共子序列長度是5，那麼這個5是怎樣得到的？我們可以通過倒向追蹤法知道5是從哪裡來的。根據遞歸式：

當Xi=Yj時，C[i][j]=C[i-1][j-1]+1;

當Xi≠Yj時：C[i][j]=max{C[i-1][j],C[i][j-1]};

則C[i][j]有三個來源：C[i-1][j-1]+1和C[i-1][j]和C[i][j-1];

在建立最優值時可以用一個輔助數組W[i][j]來記錄這三個來源：

C[i][j]=C[i-1][j-1]+1;W[i][j]=1;

C[i][j]=C[i][j-1]；W[i][j]=2;

C[i][j]=C[i-1][j];   W[i][j]=3;

這樣就可以根據W[m][n]的值來倒向追蹤，當W[i][j]=1時；輸出Xi，當W[i][j]=2時；追蹤C[i][j-1]；當W[i][j]=3時；追蹤C[i-1][j]；直到i=0或者j=0;

代碼細節：

#include<iostream>
#include<string.h>
using namespace std;
#define N 1002
int C[N][N], b[N][N];
char s1[N], s2[N];
int len1, len2;
void LCSL()
{
	for(int i=1;i<=len1;i++)
		for (int j = 1; j <=len2; j++)
		{
			if (s1[i-1] == s2[j-1])
			{
				//如果目前字元串相同，則其公共子序列的長度為該字元串前的最長公共序列+1
				C[i][j] = C[i - 1][j - 1] + 1;
				b[i][j] = 1;//标志每一步的來源
			}
			else
			{
				if (C[i][j - 1] >= C[i - 1][j])
				{
					C[i][j] = C[i][j - 1];
					b[i][j] = 2;
				}
				else
				{
					C[i][j] = C[i - 1][j];
					b[i][j] = 3;
				}
			}
		}
}
//倒向追蹤每一步的結果
void print(int i, int j)
{
	if (i == 0 || j == 0)
		return;
	if (b[i][j] == 1)//說明s1[i-1]==s2[j-1]
	{
		print(i - 1, j - 1);
		cout << s1[i - 1];
		
	}
	else
		if (b[i][j] == 2)//由上面程式可知此時s1[i-1]≠s2[j-1]且最優解來源于C[i][j]=C[i][j-1]
	{
		print(i, j - 1);//是以遞歸回源點
	}
		else 
		   print(i - 1, j);
	
}
int main()
{
		cin >> s1;
	cin >> s2;
    //字元串的長度
	len1 = strlen(s1);
	len2 = strlen(s2);
	for (int i= 0; i <= len1; i++)
	{
		C[i][0] = 0;//初始化第一列為 0 
	}
	for (int j = 0; j <= len2; j++)
	{
		C[0][j] = 0;//初始化第一行為 0 
	}
	LCSL(); //求解最長公共子序列
	cout << "s1 和 s2 的最長公共子序列長度是：" << C[len1][len2] << endl;
	cout << "s1 和 s2 的最長公共子序列是：";
	print(len1, len2); //遞歸構造最長公共子序列最優解
	return 0;
}