求解兩個(gè)數(shù)組的最長(zhǎng)公共子序列我們需要用到的知識(shí)點(diǎn)有：動(dòng)態(tài)規(guī)劃dp，遞歸算法

先來(lái)說(shuō)說(shuō)動(dòng)態(tài)規(guī)劃dp 很多初學(xué)者在學(xué)習(xí)動(dòng)態(tài)規(guī)劃的時(shí)候總是百思不得其解，什么是動(dòng)態(tài)規(guī)劃呢，其實(shí)總結(jié)來(lái)說(shuō)就是程序?qū)⒂?jì)算過(guò)的結(jié)果記錄下來(lái)，在下次使用到這條記錄的時(shí)候不需要再次計(jì)算，而可以直接使用，這樣看來(lái)是不是節(jié)省了很大的時(shí)間開(kāi)銷呢！

動(dòng)態(tài)規(guī)劃解決問(wèn)題一般套路可以分為兩步，1：自頂向下的分析問(wèn)題 2：自底向上的解決問(wèn)題

為什么要自頂向下的分析問(wèn)題呢？ 我們要知道問(wèn)題在多數(shù)值的情況下往往會(huì)具有一般性。

而自底向上的解決問(wèn)題則是因?yàn)閿?shù)據(jù)是從最底的數(shù)據(jù)開(kāi)始記錄，由少的數(shù)值計(jì)算得出多的數(shù)值。

我們可以用蓋房子為例子，工程師是負(fù)責(zé)設(shè)計(jì)架構(gòu)的，一般是從房子的頭部開(kāi)始向下設(shè)計(jì)，而建造房子則是需要從最底部開(kāi)始搭建，所以自頂向下的設(shè)計(jì)，自底向上的解決。

現(xiàn)在回到我們的問(wèn)題上，求兩個(gè)字符串的最長(zhǎng)序列，假設(shè)第一個(gè)字符串為S1，字符長(zhǎng)度為i，第二個(gè)字符串為S2，字符長(zhǎng)度為j。建立二維數(shù)組dp[i+1][j+1]，dp[i][j]的意思為第一個(gè)字符串的前i個(gè)與第二個(gè)字符串的前j個(gè)的最長(zhǎng)子序列。我們自頂向下的分析問(wèn)題即從S1的最后一個(gè)即第i個(gè)與S2的最后一個(gè)即第j個(gè)進(jìn)行判斷。顯而易見(jiàn)可以看出假如S1[i]==S2[j]相等的話那么i與j判斷完畢，接下來(lái)就從i-1與j-1開(kāi)始判斷（因?yàn)閕與j判斷完畢就往前判斷）故dp[i][j]=dp[i-1][j-1]+1。

假如S1[i]==S2[j]不相等的話，那么會(huì)出現(xiàn)兩種情況，要知道最大子序列是兩者共有的，那么i和j不相等，他們之中一定有一個(gè)不在子序列當(dāng)中，所以要么i不在，要么j不在，i不在那么我們就從i-1開(kāi)始找，j不在我們就從j-1開(kāi)始找。故dp[i][j]=max(dp[i-1][j],dp[i][j-1])。

代碼如下：

	for(int p=1;p<=i;p++)// i為S1的長(zhǎng)度       p，q皆從1開(kāi)始往后面循環(huán)                          
	{
		for(int q=1;q<=j;q++) //j為S2的長(zhǎng)度      自底向上解決問(wèn)題
		{
			
			if(s1[p-1]==s2[q-1])  //字符串從0開(kāi)始 這里容易出錯(cuò)
			{
				dp[p][q]=dp[p-1][q-1]+1;
			}
			else
			{
				dp[p][q]=max(dp[p-1][q],dp[p][q-1]);
			}
			
		}
	}

這樣我們就可以得到最長(zhǎng)子序列的長(zhǎng)度了，可以這樣我們無(wú)法得知最長(zhǎng)子序列到底是什么樣的？

想要得出這個(gè)結(jié)果，我們就需要使用遞歸來(lái)解決。

在先前我們已經(jīng)得出了dp數(shù)組的完整數(shù)值，我們可以使用dp數(shù)組的值遞歸來(lái)解決，我們先準(zhǔn)備一個(gè)空數(shù)組，假如S1[i]==S[j]，那么我們就可以直接把這個(gè)值記錄到數(shù)組里，假如他們不相等，那么就是上面的情況了分別是i不在和j不在。具體我們已經(jīng)通過(guò)dp計(jì)算出來(lái)了即dp[i][j]==dp[i-1][j]那么就是i不在序列中，我們從S1的第1個(gè)到i-1個(gè)與S2的第1個(gè)到第j個(gè)開(kāi)始尋找。dp[i][j]==dp[i][j-1]那么就是j不在序列中，我們從S1的第1個(gè)到i個(gè)與S2的第1個(gè)到第j-1個(gè)開(kāi)始尋找。這樣重復(fù)遞歸，當(dāng)i等于0或者j為0時(shí)停止遞歸。

代碼如下：

void found(string a,string b,int i,int j,char rem[],int dp[][100]){
 	if(i==0 ||j==0){
 		
	 return;
 	
	 }
 	if(a[i-1]==b[j-1])
 	{
 		rem[m]=a[i-1];
 		m++;
 		found(a,b,i-1,j-1,rem,dp);
	 }
	 else{
	 	if(dp[i][j]==dp[i-1][j])
	 	found(a,b,i-1,j,rem,dp);
	 	else if (dp[i][j]==dp[i][j-1])
	 	found(a,b,i,j-1,rem,dp);
	 	
	 }
		
	}

所以總體的代碼為：

#include<iostream>
using namespace std;
#include<algorithm>
#include <cstring>
int m;   //m用來(lái)記錄兩個(gè)字符串相等的個(gè)數(shù)
void found(string a,string b,int i,int j,char rem[],int dp[100][100]);

int main()
{
	string s1;
	string s2;
	int i,j;
	cout<<"請(qǐng)輸入第一個(gè)字符串："; 
	cin>>s1;
	cout<<"請(qǐng)輸入第二個(gè)字符串："; 
	cin>>s2;
	i=s1.length();
	j=s2.length();
	int dp[i+1][100];
	char rem[max(i,j)];
	memset(dp,0,sizeof(dp));
	for(int p=1;p<=i;p++)
	{
		for(int q=1;q<=j;q++)
		{
			
			if(s1[p-1]==s2[q-1])
			{
				dp[p][q]=dp[p-1][q-1]+1;
			}
			else
			{
				dp[p][q]=max(dp[p-1][q],dp[p][q-1]);
			}
			
		}
	}
    
	cout<<"最大子序列的個(gè)數(shù)為："<<dp[i][j]<<endl;
	
	found(s1,s2,i,j,rem,dp);
	for(int g=m-1;g>=0;g--)     //因?yàn)槭悄嫘虮４娴乃孕枰嫘蜉敵?	{
		cout<<rem[g];
	}

	
}
void found(string a,string b,int i,int j,char rem[],int dp[][100]){
 	if(i==0 ||j==0){
 		
	 return;
 	
	 }
 	if(a[i-1]==b[j-1])
 	{
 		rem[m]=a[i-1];
 		m++;
 		found(a,b,i-1,j-1,rem,dp);
	 }
	 else{
	 	if(dp[i][j]==dp[i-1][j])
	 	found(a,b,i-1,j,rem,dp);
	 	else if (dp[i][j]==dp[i][j-1])
	 	found(a,b,i,j-1,rem,dp);
	 	
	 }
		
	}

運(yùn)行結(jié)果案例如下：

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-765746.html

?

?

到了這里，關(guān)于C++ 求解最長(zhǎng)公共子序列（不僅僅求出其大?。ê?jiǎn)單易懂！?。。▌?dòng)態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！