題目六 最長公共子序列
題目描述
我們稱一個字符的數組S為一個序列。對于另外一個字符數組Z,如果滿足以下條件，則稱Z是S的一個子序列：（1）Z中的每個元素都是S中的元素（2）Z中元素的順序與在S中的順序一致。例如：當S = (E,R,C,D,F,A,K)時，（E，C，F）和（E，R）等等都是它的子序列。而（R，E）則不是。
現在我們給定兩個序列，求它們最長的公共子序列的長度。
關于輸入
一共兩行，分別輸入兩個序列
關于輸出
一行，輸出最長公共子序列的長度。
例子輸入
ABCBDAB BDCABA
例子輸出
4
解題分析
這個問題的具體描述是：給定兩個序列，求它們的最長公共子序列的長度。
程序的主要思路如下：
-
首先，程序讀取兩個字符串，存儲在
word1和word2中，然后計算它們的長度len1和len2。 -
然后，程序初始化一個二維數組
dp，dp[i][j]表示word1的前i個字符和word2的前j個字符的最長公共子序列的長度。 -
程序遍歷所有可能的
i和j（從0到len1和len2）。-
如果
i或j為0，那么dp[i][j]就等于0，因為空字符串與任何字符串的最長公共子序列的長度都是0。 -
如果
word1[i-1]等于word2[j-1]，那么dp[i][j]就等于dp[i-1][j-1] + 1。這是因為，當前的字符可以加入最長公共子序列。 -
如果
word1[i-1]不等于word2[j-1]，那么dp[i][j]就等于dp[i][j-1]和dp[i-1][j]中的較大值。這是因為，當前的字符不能同時加入最長公共子序列，所以我們只能選擇一個。
-
-
最后，
dp[len1][len2]就是word1和word2的最長公共子序列的長度。
這個程序的時間復雜度是O(n^2)，因為它需要遍歷所有可能的i和j。如果字符串的長度非常大，那么這個程序可能會運行得比較慢。
代碼實現
#include <iostream>
#include <cstring>
using namespace std;int dp[10005][10005];
char word1[10005],word2[10005];int main() {cin>>word1>>word2;int len1=strlen(word1),len2=strlen(word2);for(int i=0;i<=len1;i++)for(int j=0;j<=len2;j++){if(i==0 || j==0){dp[i][j]=0;}else{if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}}cout<<dp[len1][len2]<<endl;return 0;
}
使用記憶搜索法解決問題
#include <iostream>
#include <cstring>
using namespace std;int dp[10005][10005];
char word1[10005],word2[10005];int f(int i,int j){if(i==0 || j==0){return 0;}if(dp[i][j]){return dp[i][j];}if(word1[i-1]==word2[j-1]){dp[i][j]=f(i-1,j-1)+1;}else{dp[i][j]=max(f(i-1,j),f(i,j-1));}return dp[i][j];
}int main() {cin>>word1>>word2;int len1=strlen(word1),len2=strlen(word2);cout<<f(len1,len2)<<endl;return 0;
}
)
)
