由于本題不需要求出子序列值，所以可以進行一定程度的化簡以及優化。既然只需要求出長度，即圖中最后一行，故可以用全局變量進行記錄，將二維數組化簡為一維數組（算法導論的練習題中有提到）。思路是將一個序列固定，比如將上圖中yi序列固定不變，xi從1-m增加，即先考慮A，再考慮AB，再考慮ABC......（每次僅需要對新加入的字符進行計算）。計算方法是先判斷x[i]與y[j]是否相等，相等則（dp[i] = 上一組dp中的dp[i-1]+1），否則判斷當前dp[i]是否比dp[i-1]小，如果是，則dp[i] = dp[i-1]，否則（dp[i]=上一組的dp[i]）。dp數組在這里指y序列前i個值與x序列的LCS，隨著x序列的增長不斷更新整個dp數組。問題在與怎么保存上一組的dp[i-1]，因為計算當前組的dp[i]時是已經計算完當前組的dp[i-1]的，即dp數組前i-1個值已經更新了，所以這里需要用全局變量來維護，且僅需要維護上一組的dp[i-1]這一個值。具體維護方法見代碼中olddp和t。代碼如下：#include<iostream>#include<cstdio>#include<cstring>using namespace std;int dp[1000+5];char s1[1000+5],s2[1000+5];int main(){ int N,n,i,j,olddp,t; cin>>N; while(N--) { memset(dp,0,sizeof(dp)); scanf("%s",s1); scanf("%s",s2); for(i = 0;s2[i] != '/0';i++) { olddp=0; for(j = 0;s1[j] != '/0';j++) { t=dp[j]; if(s1[j]==s2[i]) dp[j]=olddp+1; else if(dp[j]<dp[j-1]) dp[j]=dp[j-1]; olddp=t; } } cout<<dp[j-1]<<endl; } return 0;}這里j = x序列的長度，故dp[j-1]的值即為x序列與y序列的LCS的長度。可能dp[j-3] = dp[j-2] = dp[j-1]，但是dp數組的最后一個值一定為最大值。
新聞熱點
疑難解答
