題目描述

給你一個序列X和另一個序列Z，當(dāng)Z中的所有元素都在X中存在，并且在X中的下標(biāo)順序是嚴(yán)格遞增的，那么就把Z叫做X的子序列。

現(xiàn)給你兩個序列X和Y，請問它們的最長公共子序列的長度是多少？

輸入包含多組測試數(shù)據(jù)。每組輸入占一行，為兩個字符串，由若干個空格分隔。每個字符串的長度不超過100。

對于每組輸入，輸出兩個字符串的最長公共子序列的長度。

abcd mnp

樣例輸出

0

以字符串“sadstory”與“adminsorry”為例，其最長的公共子序列(為“adsory”，長度為6。

解題思路：令二維數(shù)組dp[i][j]表示字符串A的i號位和字符串B的j號位之前的最長公共子序列，如dp[4][6]表示“sads”和“admins”的最長公共子序列長度。那么A[i]和B[j]可以分為2種情況：

(1)A[i]==B[j]，說明字符串A與 字符串B的最長公共子序列長度又增加了1位，即dp[i][j]=dp[i-1][j-1]+1。例如在樣例中dp[4][6]表示示“sads”和“admins”，因為A[4]==B[6]，所以dp[4][6]=dp[3][5]+1 即3

(2)A[i]!=B[j]，說明字符串A的i號位和字符串B的j號位之前的最長公共子序列無法延長，因而dp[i][j]將會繼承dp[i-1][j]和dp[i][j-1]，即有dp[i][j]=max(dp[i-1][j],dp[i][j-1])。例如，dp[3][3]表示"sad"與“adm”的最長公共子序列的長度，但是A[3]!=B[3]，這樣dp[3][3]無法在原有的基礎(chǔ)上延長，因此會繼承“sa”與“adm”、“sad”與“ad”的最長公共子序列的較大值，即“sad”與“ad”的最長公共子序列長度2。(這里的i,j在某種意義上來說，地位是對等的)

由此可以得到狀態(tài)轉(zhuǎn)移方程：

邊界：dp[i][0]=dp[0][j]=0 (字符串下標(biāo)從1開始，下標(biāo)0因此為0)

這樣dp[i][j]就與之前的狀態(tài)無關(guān)，由邊界出發(fā)可以得到整個dp數(shù)組，最終dp[n][m]就是需要的結(jié)果，其實現(xiàn)代碼如下：

#include <cstdio>#include <cstring>#include <algorithm>using namespace std; const int M=102;int dp[M][M]; //默認(rèn)邊界為0 char str1[M],str2[M];  int main(){	int i,j;//從數(shù)組的下標(biāo)1開始讀取字符串 	while(scanf("%s%s",str1+1,str2+1)!=EOF){		for(i=1;str1[i];i++){			for(j=1;str2[j];j++){				if(str1[i]==str2[j]){					dp[i][j]=dp[i-1][j-1]+1;				}else{					dp[i][j]=max(dp[i][j-1],dp[i-1][j]);				}			}		}		printf("%d/n",dp[i-1][j-1]);//dp[i]為'/0' 	}}
題目來源：http://www.codeup.cn/problem.php?cid=100000628&pid=0