由于本题不需要求出子序列值，所以可以进行一定程度的化简以及优化。既然只需要求出长度，即图中最后一行，故可以用全局变量进行记录，将二维数组化简为一维数组（算法导论的练习题中有提到）。思路是将一个序列固定，比如将上图中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数组的最后一个值一定为最大值。
新闻热点
疑难解答
