复杂度T（n）=T（n-1）+T（n-2）+1，T（0）=T（1）=1 令S（n）=[T（n-1）+1]/2 则边界条件S（0）=1=fib（1），S（1）=1=fib（1） 易得S（n）=S（n-1）+S（n-2）+1=fib（n+1） 可知T（n）=2*fib（n+1）-1=o（fib（n+1））=o（φn）=o（2n） T(n)=o(2n)
φ=（1+根号2）/2=1.61803
记φ36=225, φ43=230=1e9，主流计算机中约1s φ5=10，
为了解决上述问题在自顶而下递归时的复杂度问题，改为自底而上的迭代：
int f=0,g=1; while(0<n--){ g=g+f; f=g-f; }复杂度为o（1）。
子序列：由序列中若干字符，按照相对次序构成 最长公共子序列可能有多个，也可能有歧义。 序列A[0,n]、B[0,m]、LCS(A,B) 递归基：n，m=-1，取做空序列 减而治之：若A[n]=‘X’=B[m]，则取作
LCS(A[0,n-1],B[o,m-1])+'X'分而治之：若A[n]!=B[m]
return LCS(A[o,n],B[0,m-1]).size()>LCS(A[o,n-1],B[0,m]).size()? LCS(A[o,n],B[0,m-1]):LCS(A[o,n-1],B[0,m]);课程中并未给出具体代码，这里给出仅供参考：
#include<iostream> #include<string> using namespace std; string LCS(char A[], char B[], int n, int m){ if(n==-1||m==-1)return "";//有一个数组为空 if(A[n]==B[m]){ return LCS(A,B,n-1,m-1)+A[n];//最后一位相同，去掉最后一位，前面继续比较 }else{ return LCS(A,B,n,m-1).size()>LCS(A,B,n-1,m).size()? LCS(A,B,n,m-1):LCS(A,B,n-1,m);//最后一位不同，取得较长的子序列 } } int main() { char A[]="daea"; int n=sizeof(A)/sizeof(A[0])-2;//获取最后一位序列 char B[]="dlta"; int m=sizeof(B)/sizeof(B[0])-2; cout<<LCS(A,B,n,m)<<endl; system("pause"); return 0; }与fib函数类似，仍有大量重复递归，，因此也可采用迭代方式： 假想的将所有问题列成一张表，从LCS（A[0],B[0]）出发依次计算所有项 课程中依旧没有给出代码，我尝试写了一下，这个代码只能解决只有一个解的问题，当出现多个解时，便会出现错误，有待优化。
#include<iostream> #include<algorithm> #include<string> using namespace std; void LCS(string a, string b){ int p[100][100]; memset(p,0,100); int n=a.length(); int m=b.length(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){//生成假想表格 if(a[i]==b[j]) p[i+1][j+1]=p[i][j]+1; else p[i+1][j+1]=max(p[i+1][j],p[i][j+1]); } } string c=""; int k=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){//从假想表格中挑出子序列 if(p[i+1][j+1]==p[i][j+1]+1&&p[i+1][j+1]==p[i+1][j]+1) { c=c+a[i]; } } } cout << c << endl; } int main() { string a,b; a="absd"; b="cead"; LCS(a, b); system("pause"); return 0; }