Fibonacci数列和动态规划

什么是Fibonacci数列？

Fibonacci数列指的是这样一个数列

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,144, ...}

它的第0项是0，第1项是第一个1。从第二项开始，每一项都等于前两项之和。用C语言可以表示为：

//Fib(n) = Fib(n-1) + fib(n-2)
int Fib(int n) {
         return(2 > n) ? n : Fib(n-1) + Fib(n-2);
}

这段代码可以计算出Fibonacci数列的第n项。但是随着n的增长，它所消耗的时间逐渐让人无法接受。可以推算出它的时间复杂度为：

T(0) = T(1) =1; T(n) = T(n-1) + T(n-2) + 1,n > 1;

令  S(n) = [T(n) + 1] / 2

则  S(0) = 1 = Fib(1); S(1)= 1 = Fib(2)

故  S(n) = S(n-1) + S(n-2)= Fib(n+1)

      T(n) = 2 * S(n) – 1 = 2 * Fib(n+1) – 1 = O(Fib(n+1))= O(Φⁿ) =O(2ⁿ)

这是一个指数级的复杂度。

O(Φⁿ)具体有多大？

Φ⁴³ =2³⁰= 10⁹ flo = 1 sec

Φ⁶⁷ =10¹⁴flo =10⁵ sec = 1 day

Φ⁹² =10¹⁹flo = 10¹⁰ sec =10⁵ day = 3 century

如果用以上算法求Fibonacci数列的第67项需要1天，求出第92项则需要整整三生三世！

为什么会这么大？

使用递归跟踪将Fib(5)的调用关系绘制如下图：

可以发现其中许多项被重复调用多次，总共O(Φⁿ)种递归实例去除重复后只有O(n)种。

该如何改进？

改进方法A 记忆法（memoization）：将已经计算过实例的结果制表查备。代码如下：

int memoir[100];
int Fib(int n) {
         if(memoir[n] < 0)
                   memoir[n]= (2 > n) ? n : Fib(n-1) + Fib(n-2);
         returnmemoir[n];
}

改进方法B 动态规划：颠倒计算方向：自顶而下递归改为自底而上迭代。代码如下：

int Fib(int n) {
         intf = 0;
         intg = 1;
         while(1 < n--) {
                   g= g + f;
                   f= g - f;
         }
         returng;
}<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);"> </span>

这两种改进后算法的时间复杂度均为O(n)，记忆法的空间复杂度为O(n)、动态规划的空间复杂度为O(1)。

LCS和动态规划

什么是LCS？

LCS是Longest CommonSubsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。

如何求出LCS？

对于序列A[0, n]和B[0, m]，LCS(A[0, n], B[0, m])有三种情况

若n = -1 或 m = -1，则取空序列""

若A[n] = B[m] = ‘X‘，则取LCS(A[0, n), B[0, m))（减而治之）

若A[n] ≠ B[m]，则在LCS(A[0, n], B[0, m))和LCS(A[0, n), B[0, m])取更长者（分而治之）

LCS的每一个解，对应于(0, 0)和(n, m)之间的一条单调通路，反之亦然。例如LCS("advantage", "educational")的求解过程如下图：

LCS的单调性：无论如何，每经过一次比对，原问题的规模必可减少，作为输入的两个序列，至少其一的长度缩短一个单位。

LCS的性能如何？

根据上边提到的三条分支，可以构建出一个递归LCS算法，代码如下：

int LCS(const char *A, const char *B, int n, int m) {
	if (n < 0 || m < 0)
		return 0;
	if (A[n] == B[m])
		return LCS(A, B, n-1, m-1) + 1;
	int result1 = LCS(A, B, n-1, m);
	int result2 = LCS(A, B, n, m-1);
	return result1 > result2 ? result1 : result2;
}

int main() {
	const char *A = "aadvantage";
	const char *B = "educational";
	
	printf("%d", LCS(A, B, strlen(A)-1, strlen(B)-1));
	
	return 0;
}

如何改善LCS？

跟Fibonacci数列类似，LCS算法也可以从递归转为迭代，由前缀向后推算。这样能把时间复杂度从O(2ⁿ)降为O(m*n)。为此只需要将所有子问题列成一张表，颠倒计算方向，从LCS(A[0], B[0])出发，依此计算出所有项，如下图所示：

迭代LCS代码参考如下：

int table[20][20];
 
int LCS(const char *A, const char *B, intn, int m) {
         inti, j, max;
         for(i=0; i<=m; i++) {
                   if(A[0] == B[i])
                            table[0][i]= 1;
                   else
                            table[0][i]= 0;
         }
         for(j=0; j<=n; j++) {
                   if(B[0] == A[j])
                            table[j][0]= 1;
                   else
                            table[j][0]= 0;
         }
        
         for(i=1; i<=m; i++) {
                   for(j=1; j<=n; j++){
                            max= table[j-1][i] > table[j][i-1] ? table[j-1][i] : table[j][i-1];
                            if(B[i] == A[j])
                                     table[j][i]= max + 1;
                            else
                                     table[j][i]= max;      
                   }
         }
         return table[n][m];
}

注：本笔记来自清华大学邓俊辉老师的MOOC课程《数据结构》，感兴趣的朋友点击这里选课学习。

[MOOC笔记]第一章XA 动态规划(数据结构)